Du solltest vergleichen, ob dein Public Key in den Mails vom Server mit dem Public Key der lokal bei dir im Mailvelope angezeigt ist übereinstimmt. Ob du sonst noch was machen musst, müsste im Mail stehen. Da ich selbst meinen Testkey nicht publiziert hab, kann ich dir da nicht weiterhelfen.
Wenn im "Neue Nachricht"-Dialog nicht das Blatt/Stift-Symbol angezeigt wird, versuchs mal mit dem Mailvelope-Icon, Erweiterte Optionen -> auf dem aktuellen Tab aktivieren. Ansonsten... eben, habs selbst nur angetestet.
Und allen löblichen Bemühungen von GMX, web.de und anderen zum Trotz komme ich einmal mehr zum Schluss, dass es leider immer noch keine wirklich allgemeintaugliche Möglichkeit zur End-to-End-Verschlüsselung von E-Mails gibt.