Mail just stopped returning search results when I did a full text email search. I did a bit of googling and found some discussion on the problem with 10.4.7 that was fixed with 10.4.8. So, not that. Someone in that thread mentioned that they forced a re-index of their entire drive in Spotlight.
Scott, another individual who mentioned the problem on his blog said he attempted to just re-index the local Mail repository, but to no avail (he noted that there was a problem with the Spotlight filter for Mail). He also forced a rescan of the drive.
I didn’t feel like doing an entire rescan, so I checked for the Spotlight filter with mdimport -L. Lucky for me, the Mail importer seemed to show up. I quit Mail, re-indexed its data with mdimport -f ~/Library/Mail, waited a few minutes and re-opened Mail to find search working again.
So, just forcing a re-index of the Mail directory seems to work under 10.4.8 Intel.