Apparently there is no official way to clear or fix the suggestions that come up in the iOS Mail app when you start typing the name of someone to send email to.  And it’s not clear how it’s sorted, because when typing a single character, the most commonly used addresses are not at the top, nor is the list in alphabetical order.

If you want to clear out this auto-suggest database, and want to take your iOS life into your own hands (if this doesn’t work you could lose data, because we’ll be doing a restore) then here’s what you can try:

• Back up your iThing using iTunes
• No really, back it up – Sync is useful, but to be sure right-click on your device and select Back Up
• Go into your home directory in the Finder, then Library, Application Support, MobileSync, Backup
• Change to the list view and sort by Date Modified
• The most recent date should have a timestamp of just now, and is the backup you just made
• Look inside there and find the file that starts with 31bb  (31bb7ba8914766d4ba40d6dfb6113c8b614be442 to be exact)
• Move it someplace else, like your desktop
• In iTunes, you want to Restore your device and then reload it with the backup you just made
• There will be an error saying that a file is missing and it won’t work – just click okay and let everything finish
• When this is all done, you will have no email auto-complete suggestions at all!  Which is better than nothing, but kind of sucks that this is the only way to fix problems that come up

Remember – this process nukes your phone and restores from a backup!  If you’re not comfortable with that, don’t do it!  I’m not sure how you’ve got your iTunes/iThing set up and so 100% of your stuff may not back up and be restored.  Good luck!  :-)