Old post is old, sorry for reviving
This is the first thread to turn up on google in regards to entourage spotlight not working.
A year ago I had this problem and struggled to fix it, now, a year later I had the problem again, but forgot how I fixed it. After struggling for a bit, I remembered what I had done before.
This may not be the case for everyone, but for me, the problem wasn't because of entourage, it was because of OSX's own spotlight database. I had manually done it via terminal before (deleted old stuff and rebuilt new spotlight database), but this time I tried a little app called "Maintenance" (v 3.8 at the time of this writeup). I simply chose the rebuild spotlight index option, and ran it. A couple seconds later it gave me a notice that it had completed, then, if you click the spotlight button up on the top-right-hand-side of your mac, you'll notice it shows that the database is rebuilding. I went to lunch, came back, and it had completed.
I performed a search in entourage, and, much to my satisfaction, everything worked again.
The download link to this utility is here:
http://www.apple.com/downloads/macosx/automator/maintenance.html
I hope this helps someone else out there, as it managed to frustrate me twice now.