I'm pretty sure the only way to get rid of it is to do a hard reset. Which sucks if you replied to a few people in Craigslist -- they now show up in your email history forever.
Speaking of which, the OS will also duplicate contacts in your history list if they write their names different than what's in your contact list. For example, say I have the name Doe, John stored in my contact list. However, they have their name set up to be read as John Doe when they send emails. If I reply, John Doe is now stored forever in my email history as well. So, whenever I start typing in John's name, both Doe, John and John Doe show up in the history even though they have the same email address.
Kind of annoying, I agree. I'm hoping they will change it in future iterations. I posted a suggestion to fix this on their website awhile ago, I think. Last I checked though, no one voted for the feature. I would rather them only list email addresses that are present in my contact list.
Thankfully, compared to my experiences with Android and iOS, this problem is peanuts. But still...