Deleted contacts appear in auto complete

I have a problem where contacts that have been long since
deleted from my outlooks contacts list keep re-appearing
in the auto complete list when I start typing freehand
into the To: box, yet when I try to find this contact to
delete their details completely “again” I can’t find
them. Can anyone help me with my problem ?

Thnx in advance…….
.