Taken from the dpkg bot on #debian:

gpg --keyserver subkeys.pgp.net --recv-keys <key> ; gpg --export <key> | sudo apt-key add -;

where key is the key ID reported missing from aptitude