Right. Well, now I'm sad because I realized that indeed I had this problem occasionally; the way GMail implements search I don't exactly even trust them that the first mail they show me is actually the first mail, and not search bugging out. I guess I forgot about that because I very rarely need to do such a search.

You also reminded me of another e-mail annoyance - people sending PGP signatures in attachments make it nigh-impossible to search for actual attachments, as every conversation with those senders looks like it has one.