Estou respondendo minha própria pergunta aqui, caso alguém tenha um problema semelhante.
Minha solução foi inicializar python-gnupg com um novo homedir. Esse novo homedir agora pertence ao usuário root
porque o script é executado como root.
Dessa forma, tudo o que o script faz é independente da instalação do gpg que eu acesso ao digitar gpg [command]
no terminal. E não há mais erros ao pesquisar servidores de chaves.
Portanto, alterar o código python acima faz o trabalho:
import gnupg
gpg= gnupg.GPG(gnupghome="/home/pi/gnupg_myscript")
keyserver= "pool.sks-keyservers.net"
search_string= "[email protected]"
print gpg.search_keys(search_string, keyserver)