Dazu musst du die Schlüssel digital signieren lassen. Heise macht dies im Zuge der Kryptokampagne auf Messen etc kostenlos.
Dort füllst du ein Formular aus, gibst deine Personalausweisnummer an, diese wird von einem Heise Mitarbeiter verifiziert und Heise garantiert dann dafür, dass der Schlüssel dem wirklichen Eigentümer gehört.
Das ganze gibts natürlich auch kostenpflichtig von anderen Zertifizierungsstellen.
Wenn dir allerdings dein Gesprächspartner seinen Fingerprint per Telefon mitteilt, sollte es da eigentlich keine Probleme geben, den wahren Absender zu identifizieren