Many! Many iPhone users who have upgraded to iOS 5 or iOS 5.0.1 using either Apple iPhone 4S, iPhone 4 or iPhone 3GS have reported that the Spotlight Search feature is not working for their Phone. iPhone 4 and iPhone 3GS users have reported that it was working fine when they were on iOS 4 and when they upgraded to iPhone iOS 5 it worked for some time but then it stopped working.
The problem seems to be in Indexing of Emails, that is iOS 5 has some kind of error when there are lot of Email is in multiple Accounts specially when there is an exchange account synced. So it’s not that your Spotlight search is not working it is just taking lot of time indexing the Emails
Go to to Settings> General > Spotlight and untick the Email Option and it should start working and for Searching Emails there is a search options in Email App as well.