From everything I have searched for on this topic shows that you have to restore your device as new from your desktop/itunes. Unless they just recently fixed this. It is very annoying I agree. It would be nice to have a button to clear the cache of previous email recipients!
If you get iBackupbot, which has a free trial, you can pull out your backup, check the emails, delete the addys you don't want, then restore that backup.