David Bremner <david@tethera.net> writes:
>> I click on it, and it requests _my_ public key from the key server, and
>> of course nothing changes - because I already had the key.
>
> So after you click, the key downloads, and the button does not change
> colour?

Yes. After it downloads, it still says "Unknown key KEYID or unsupported
algorithm". I would be confused by the unsupported algorithm - it is
just an RSA/RSA key, newly created. This has also happened for other
signed messages - it downloads the key, but still says it doesn't know
the key (and this persists across restarts of emacs).

>> Any ideas? Is this because of some missing package or misconfigured
>> setting? I'm using the latest released version of notmuch (0.15.2),
>> emacs 24.2.1, and gpg 1.4.11.
>
> Does using easypg from within emacs work for you? You can try with 
> "M-x epa-list-keys"

That works, and it shows the key there.

One thing I forgot to mention - I have notmuch running on a remote
server through ssh. I don't really imagine this would be an issue, but
maybe? (I also have the library installed locally, for emacs).