Na ja es gibt viele öffentliche Schlüsselserver. Daher kann es sein, das

die vielleicht wo anders ihren öffentlichen Schlüssel hingeladen haben oder du den auf Anfrage beim Empfänger bekommst.