How to: Search Old MobileMe Mail on the Server
select your Inbox or another folder from your MobileMe Mail account and access the search field by scrolling to the top of the message list. (Tap the status bar at the top to quickly reveal the search field.) Type what you want to search for and tap To, From, or Subject, or All to search all three. You'll see the messages that match the search on your device, and you can then tap "Continue Search on Server" to see the remaining messages that are stored in the MobileMe cloud.
I've used this to find old order info, network machine names, and scads of other stuff buried in server-side email. Since it doesn't (yet?) search the body of the email, it's not as useful as Gmail's WebApp, for example, but it's lightyears ahead of where it was under 2.2.1.