Mac question

I've been asked to employ the LJ brain trust on a weird Mac problem.

New Mac. Running Leopard.
When trying to search email it's only searching the to: from: and subject: fields and not the whole of the messages.

Apparently this is the exciting new Mac bug.
"rebuilding the Spotlight index so that your searches will live again!" has already been tried
(http://www.macosxhints.com/article.php?story=20080201111317585)

Apparently totally random solutions work for different people.

Anyone got anything?