That's elementary, but often overlooked: use the arrow keys to go down to the address you do want to delete, then press on delete-key to delete. These entries aren't from the address book, but from some history defined elsewhere. And this is the way to delete it.
Hope this helps.
Kees
Outlook 2002 Windows XP SP2
Creating a message : when I enter the first few letters of a name in the TO field Outlook suggests the good E-mail address and E-mail addresses which are no longer in my address book for the contact. How can I delete these unwanted entries ?
Thank you for your help.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic