using gnupg with mutt

[Zenaan Harkness]

Does anyone know how to have an automatic association between a pgp
public key and a 'specified by me' email address?

As in, some people create gpg keys which do not include their email
address, and I would have thought it trivial for me, in my own keyring,
to associate a public key I have received, with one or more email
addresses of my choosing (and / or the person's name, as fair as I know
the name etc).

gpg --edit-key HASH
brings up a prompt, and help gives things like trust and list, and there
is a "notation" sub command which sounds perfect for the job, but can
only operate on private keys, not public keys.

This all does not make sense to me. When someone sends me an email,
signed with their private key, and I get a copy of their public key, I
should be able to associate their public key, with their email address,
even if their own signing of their pub/sub public key does not include
that particular (or any) email address.

What gives?

TIA