This one has been bugging me for a while now too. This evening, I had time to try some things. All to no avail, but just to share my findings:
1. When I rebuild my Spotlight index, I can search within entire messages for a while. However, while the Spotlight indexing still goes on, somewhere along the way something goes wrong: the same search query which previously returned some 80 hits, suddenly literally turns up empty. Mind you: while the previous run of the query still is on the screen! I merely do a refresh ([ENTER]) of the query! Console logs nothing which indicates any problem.
2. When I kill mdworker-processes and mds from within the Activity Monitor, I can search within entire messages exactly ONCE. After that one, glorious time, it's over again. And also here, Console doesn't log anything of value.
I asked a colleague who switched to Lion recently, and he experiences the same thing (although he wasn't aware before).
Anyway, I gave this as a feedback to Apple. I'm sure they are aware of this flaw within Apple Mail 5, but it'll never hurt to put some emphasis on this. I asked my colleague to do the same.