L'autocompletamento usa solo gli indirizzi in rubrica, quindi hai probabilmente attiva l'opzione che aggiunge automaticamente gli indirizzi della posta in uscita.
Vai in Strumenti --> Opzioni --> Composizione --> Indirizzi e disabilita "Aggiungi automaticamente ecc."
Devi anche cancellare gli indirizzi che hai aggiunto finora, li trovi probabilmente nella rubrica dal nome "Indirizzi collezionati"