Bei der Deinstallation des alten Outlook werden zwar die Programmdateien, jedoch nicht die Daten entfernt.
Die alten Mails solltest du unter
Code:
C:\Dokumente und Einstellungen\%username%\Lokale Einstellungen\Anwendungsdaten\Microsoft\Outlook
finden und ggf. entfernen können.
Ob es dadurch zu einem direkten Zusammenhang mit dem Autovervollständigen kommt, kann ich hier nicht nachvollziehen, da ich Office2007 nicht unter XP benutze.