diff --git a/guix/gnupg.scm b/guix/gnupg.scm
index c17a495..ba5160a 100644
--- a/guix/gnupg.scm
+++ b/guix/gnupg.scm
@@ -143,7 +143,9 @@ missing key."
        status))
 
 (define (gnupg-receive-keys key-id server)
-  (system* (%gpg-command) "--keyserver" server "--recv-keys" key-id))
+  (system* (%gpg-command)
+           "--keyserver" server
+           "--search-keys" (string-append "0x" key-id)))
 
 (define* (gnupg-verify* sig file #:optional (server (%openpgp-key-server)))
   "Like `gnupg-verify', but try downloading the public key if it's missing.