Hi Paula,
Although you've removed the addresses from your contacts, Outlook still has them cached for use with the "AutoComplete" feature. You can remove them from AutoComplete by starting to type the name, then when it appears in the AutoComplete list, select it by using the Up and Down arrows, then press Delete.
Hope that helps.
Jenifer