I've tried all of the suggestions on this thread thus far, including enabling Locate via Terminal which is off in Lion by default, some type of Security hazard/restricting (blah, blah, blah for home users). Nada, nothing, zilch got me squat. I've even reinstalled Lion over Lion. I'm on Lion 10.7.4 and an avid die hard Apple fan to the core and a .Mac/MobileMe/iCloud user. All my stuff is synced with Apple. So imagine the pain, frustration and fn headaches. Mail wouldn't find my name, my Apple ID user name, nothing..... So I tried and tried, rebuilt this rebuilt that, used Onyx, used MacPilot, used ACLr8, Disk Utility, Snow Leopard install disk utility from boot, resetting ACL's. Finally a trio of commands worked for me.
Close the Mail application first before any of this, even better close all open applications except terminal until finished with these commands.
1. Open terminal and use this, it will ask you to authenticate: sudo mdutil -E /
2. Then at the next command prompt enter this, it will ask you to authenticate: sudo mdutil -i on /Users
3. Open up System Preferences and go to Spotlight. Under "Search Results" mark all the boxes if not marked already and then drag "Messages & Chats" to the top so that it is first. If it's already first I guess you can try to drop it to second and that might work. It wasn't first for me but I drug it there anyways. Then close System Preferences.
Now close/exit Terminal and then open up Mail. If you were as lucky as me and typed in a search term you know there is a cr*p load of, then you should be smiling at all the results like I did. I can't believe that I was almost so desperate that I almost said out loud that I would start using Outlook 2011 for Mac and HoudahSpot if this didn't work. Those are some serious words to say out loud, at least for me.
Good luck and God I hope this helps another down-trodden, beat up Apple Lion user like myself, who happens to have 80,000+ e-mails stored since 2002 using Mail.