One great reason not to use Entourage is that it has One Big File which contains Everything. Messages are not saved as individual files (as they are in Apple's Mail), and thus, cannot be backed up individually by Time Machine.
You can try the following:
Quit Entourage.
Locate your Entourage database.
Move the Entourage database file out of its regular location - say, to the desktop. DO NOT DELETE IT.
Restore the database file from the Time Machine backup from before you deleted the message in question.
Turn off your Airport/unplug your network cable (you don't want new messages downloaded into the old database).
Open Entourage, locate your e-mail and export it, or copy the text to a TextEdit document, a Note, or whatever.
Quit Entourage.
Replace the restored database with the original one (that you moved to the desktop) and restart Entourage.