The autofill might also be remembering past addresses you've typed (or mistyped), but aren't necessarily saved in your Contacts. That might be in the Email app's cache/data, or the keyboard app's cache/data. Try clearing your email app's cache first, then your keyboard app's cache, and see if either of those steps help. If they don't, then try clearing the email app's data -- this will likely require you to add your email accounts back to the email app again, but assuming you're using IMAP servers, you won't have lost any email data, since it'll just resync. If that still doesn't work, then clear the keyboard app's data (which might clear out any saved personal dictionary items, so use caution if you have a ton of those that don't sync anywhere, like your Google account).