Lustigerweise ist die hier als "Lösung" markierte Antwort von marcus - zumindest was Outlook angeht - nicht zutreffend.
Die Vorschläge (Auto-Vervollständigung) werden nämlich in Outlook unabhängig vom Adressbuch gespeichert.
Die tatsächliche Lösung in Outlook besteht darin mit der Maus über den falschen Vorschlag zu "hovern", dann 'Delete' drücken, oder das Kreuz links daneben, falls es angezeigt wird.