I use office 2004 (with latest update) and had similar problems after upgrading to Mac OS 10.5 Entourage was set to allow spotlight searches but nothing appeared in spotlight searches from the icon in the header bar. With some tweeking I was able to search with spotlight opened within a finder window (apple option key f) but had to reset search criteria every time to include system folders.
I rebuilt the entourage database and deleted unwanted older versions leaving the 2 most recent.
Then I deleted all sub-folders and their contents from the folder "2004" This contains the metadata produced by spotlight when it indexes your entourage mail. It is in the metadata folder within the caches folder of your username library.
I then opened spotlight preferences and dragged my hard disk icon from the desktop to the privacy pane. I closed preferences and rebooted. I then removed my hard drive from the privacy pane and rebooted again. This forced spotlight to reindex the hard drive including entourage mail folders. The metadata folderw were rebuilt and, at least for now, the contents of my entourage mail folders appear in spotlight.
This worked for me after some experimenting. Maybe not all these steps are required. I took the usual precautions of backing up and repairing permissions.