I know this happened on my wife's iPhone and this recently happened to my iPhone (again). The email address auto-complete started to fail. It used to be: I click in the To: field and type "e" and my wife's name and email address would pop up. Just a few days ago, this stopped working -- very annoying. I tried clearing the user dictionary, but that didn't work. I tried a reset and that didn't work. I tried restoring my iPhone and then restoring my settings -- that didn't work. The only thing that worked? Restoring my iPhone to factory without restoring from a backup. Very annoying! Apple needs to create a way of letting users "forget" or reset the auto-completed address cache. Auto-complete is very useful, but it shouldn't take a complete restore of the iPhone in order to make it work again!