Forgive me if this is too painfully obvious, but since Entourage will make a new database/user at start-up if it can't find the old one ... it might appear that your database is gone when in fact, you just need to find it and repoint the app there. I would do that, once I found it, by "switching users" and once "switched" ... just trash the db it just made.
How to find yours? There are so many levels of expertise at Spotlight, I'm going to suggest downloading EasyFind by Devon Technologies -- it's free, and will find anything on your disk. Period. There are very few preferences, and one setting is to just search everywhere for anything.
Entourage usually keeps the folder " Microsoft User Data" in the your User/Documents folder, if I remember correctly ... oddly enough, it is also perfectly happy in User/Library/Preferences, where mine has been for so long ...
I suspect you haven't lost your mail at all. If, in fact, you really, truly have, I recommend you download trials of DataRescue and FileSalvage, which of course work as unerase utlilities, and see how you make out. Good luck!