Entourage doesn't use spotlight to search for mail within the application, however there is a setting to include entourage emails when doing a spotlight search from the spotlight menu.
Mail has this right on. I don't think I've ever had an issue with not finding something. One time maybe but refreshing the spotlight index with mdutil fixed it.