I found another issue with the search function. I've noticed the search results do not include email messages placed in an archive folder I've created on my mac. Only messages which are located in the actual inboxes and sent items are included in the search items.
I can also confirm that the "from" list is incomplete. I've the idea that only contacts which are listed in the MS Exchange directory (of my university) are listed, in addition to my own contacts. Senders which I haven't saved in my contact list are missing.
Interesting to not is that spotlight is able to find the messages which are not listed via the Mail search.
Another thing: "entire message" does not include sender information: for instance, mails from dropbox only show up if I select "From", but not when I select "entire message". This is counter intuitive in my opinion. BTW, I just see that the term "dropbox" is almost always included in the main text, so it should show up, even if "entire message" does not search through the "From" section.
I find the new search function quite horrible to use. I hope someone is able to point out what I'm doing wrongly.
UPDATE:
I just created a new mailbox and moved a couple of "old" (pre-lion-received) messages which I was not able to find previously into the new mailbox and guess what happened: I now am able to find via the search funciton
UPDATE 2:
I think something went wrong when I upgraded to Lion. I've rebuilded all my old mailboxes and it now works fine. You can do the same by selecting your mailbox and click Mailbox -> Rebuild.
Message was edited by: Morrey