Unwanted contact

When insert the first letter, the name of someone I deleted from the contact list pops up. How do I get rid of it?

These addresses are automatically saved in the Recipients History. You can edit the list and settings in Menu > Tools > Settings > Mail > Compose > Recipients History.