you beat me to the punch bro. i had the exact same issue and it was the developer of houdahspot who helped me with this. his email (here for reference and credit) said:
"Hi!
Please locate one of the emlx files. Then use the Terminal.app command line to run the following command on that file. You may drag and drop it from the Finder to get the correct path.
mdimport -d4 /path/to/file.emlx
This does two things:
1. It forces Spotlight to import the file
2. It prints a lot of debugging information
The first part of which is of little interest: list of available importers, …Next Spotlight says which importer it chose to whorl on the file.
Lastly you get the output from said importer. This is the metadata which Spotlight will index and which thus will be searchable.
You would expect to see:
(Info) Import: Importing type 'com.apple.mail.emlx' using 'file://localhost/System/Library/Spotlight/Mail.mdimporter/'
Meaning: Apple's importer is used to index the file. If it is another one, that is likely at fault.
In the values, look for kMDItemDisplayName. That is the name displayed by Spotlight.
Best,
Pierre Bernard
Houdah Software s.à r.l."
i would like to add that i ultimately decided that i wanted to have a clean install of lion on my new macbook air to avoid issues like this and an now i am slowly manually migrating and reinstalling my apps and settings. its a bit of a pain but if you can afford a bit of time and can be patient you may benefit in the long run.
on my upgraded macbook pro that i am still using i where i installed lion the above fix was absolutely required.