So, wie Du das beschreibst, ist das bei mir dann auch. Erst dann, wenn ich den Kontakt lösche und lege diesen wieder manuell an, kann ich ihn finden in der Auswahl für eine neue Email.
Hinzu kommt, dass die Suchfunktion im Bereich Kontakte zumeist überhaupt keine Ergebnisse liefert.