....try the old voodoo of using Disk Utility to Repair Disk and Repair Permissions.
I've done that, using my clone drive, but it doesn't change anything.
I've also, in addition to re-indexing with Onyx, used TechTool Pro 6 to rebuild the directory and optimize files and the volume. After optimization I re-indexed again. So far I've done pretty much everything, except stand on my head and spit nickels, and nothing changes.
I could live with Spotlight not finding folders in Mail as I pretty much know where they all are. However, if Spotlight isn't working properly, the concern becomes "What is it not finding on other searches?" I did a couple of quick searches with words that should have returned a pile of results but got minimal results.
EDIT: I'm now wondering if there is a more 'global' issue that's affecting searches. I just downloaded EasyFind to see what it would do.
I gave EasyFind a three word phrase that I know is in more that 100 Word documents and I asked it to look in Files. It didn't find even one.
I then asked it to find, using any of the words, and It found a pile of stuff but still not one of the Word documents.