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.