This is something I've seen others complain about on here, as well as myself. Before, if you typed a letter when addressing an email, you'd see all the email accounts you've ever sent an email to. To remove these you had to restore as new as that was the only way to get these deleted from Mail. Now, Apple gives us an easy way to remove them. Just click on the > button and you'll be given the option of Create New Contact, Add to Existing Contact, or Remove From Recents. EDIT** It appears they are also synced via iCloud. I just opened my iPad which had a few for the letter 'A' and now they are gone even though I didn't remove them from the iPad, just the iPhone.