I've got a solution that will work on OS X, Linux, BSD and other *nix systems, but if you're on Windows you might be out of luck (or need to go to a little more effort).
Go into Thunderbird and open up the address book. There will probably be at least two sub-sections: personal addresses and collected addresses. There may be more. Highlight each of these sub-sections, go to tools and select export, name the file something appropriate and repeat the process for each sub-section of the address book. The export creates .ldif files containing all the details of every contact in plain text.
For this example I'm saying that I saved two files as /tmp/personal.ldif and /tmp/collected.ldif for the main address book sub-sections. Then it's time for a little work in a bash prompt:
cd /tmp/
grep "^mail: " personal.ldif > pmail.txt
grep "^mail: " collected.ldif > cmail.txt
Then open /tmp/pmail.txt and /tmp/cmail.txt in the text editor of your choice and fo a find/replace on "mail: " with nothing (i.e. ""). Then back to our little shell prompt to finish with:
for x in `cat pmail.txt` ; do
gpg --recv-keys $x
gpg --keyserver pgp.mit.edu --recv-keys $x
done ;
for x in `cat cmail.txt` ; do
gpg --recv-keys $x
gpg --keyserver pgp.mit.edu --recv-keys $x
done ;
Depending on how many email addresses are in your contact lists, that might take a while. Most of the responses will be failures, but you can just let it run in the background.