Yesterday, I spent roughly 25 mins to look for an email on my iPhone. I needed to call a friend and his phone number was in that email.
Even though it should be obvious by now, email interface on iPhone should provide an interface for searching through email. Considering that IMAP4 (the standard protocol that is used to download emails from the email server to any device) provides search capability, it shouldn't be hard to implement this feature. I hope to see this in new release of software on iPhone.