Deleted email contacts still appear! HELP

I permantly deleted contacts on my Yahoo address book and on my Iphone. But when I hit mail and start typing a name those deleted contacts still appear!! I've tried everything! I've synced it, cleared cached, clear history, deleted and reactivated my email accounts, cleared ALL in Autofill. Besides restoring the whole phone, how can I get rid of them? Why do these deleted contacts still appear? Please help

Here's one way to get rid of unwanted contacts How to Delete an Email Address from Auto-Complete in Mac OS X Mail - About Email. There are similar ways to delete multiple contacts. How to Clean up Mac OS X Mail's Auto-Complete List - About Email

But what about the iPhone?

Thanks for your reply but those links are for Mac computer users. How do I delete them from my iPhone?

Only way I know of to do it currently is by restoring the phone. A liitle much for most. Let's keep our fingers crossed that 4.0 will have a way to edit these.

Anyone else know how to deal with this on the iPhone?
Having the same issue with ALL my iPhones since I bought my first iPhone a few years ago. Many friends and family have changed their E-mail addy's, I've deleted those from my contacts on the iPhones, performed full restores, even gone through few iPhones with complete restores since then, but those old defunct addy's are still in the autofill and my fat thumbs sometimes accidentally get selected! I sync wthi my iMac, but have not even set up MAIL on my iMac, (web based E-mail only) so I know it nots from the iMac mail.

How is the auto fill memory on the iPhones purged, deleted etc?

Paul
iPhone gen1, os 3.xx
iPhone 3g os 2-3-4.01
iPhone 4 os 4.01