Up until iOS 6, there was no way to remove e-mails from the "recently contacted" list when you start typing new e-mails, even if that person wasn't in your Contacts. Now, you can remove them one at a time, provided they are not in your Contacts.
All you do is start typing the e-mail address, and then when the list of addresses starts to populate the screen, scroll down to the address you wish to delete. It will have a blue arrow pointing to the right. When you tap on that arrow, you'll see a Remove From Recents button; tap that to remove that e-mail address from the recent e-mail list.
[kirkmc adds: I don't know if this is new in iOS 6, because I never really paid attention to it. What I notice is most of the addresses I see are addresses I've used on my Mac, not on my iOS devices. So, I went into Mail > Window > Previous Recipients, and deleted all those who weren't in my Contacts, and the next time I synced my iPhone, those extra addresses were gone.
Note that I sync e-mail accounts via iTunes (Info tab > Sync Mail Accounts); if you have only set up your accounts on an iOS device, and don't sync, then this my work differently. Can anyone post in the comments if they do it differently, and if e-mail addresses get deleted after removing them in Mail?]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20121109125424787