Is there a way to clear this list somehow? I switched jobs recently and removed a ton of old work related contacts. But there email addresses still show up when you type in an email address when composing an email.
I figured it out, go to settings, general scroll down to reset, then reset network settings and location settings. Your iPhone should be working now.
Edit:
If that doesn't work just reset the while iPhone. (don't not erase the iphone at all unless you backed up all your information, this will take about 2 hours or so. After that is done just resync your iPhone to your mac or pc).