Every time I write a new email message to a contact listed under S another email address for a deleted contact still keeps popping up in the drop down box.

This person is not in my contact list and all emails from and to them are deleted. So why can't I get rid of their email address?