Generally, you'd need to have a match (or chain) between keys you do trust and those signing a given key.

In general, I fetch signatures of keys and may add some of these as partially trusted if they're very well known keys.

A bit of bash scripting that helps with this:

    gpg --list-sigs <key ID>  | grep 'not found' |
        cut -c 13-22 | sort -u |
        xargs --max-args 10 gpg --recv-keys

xargs speeds the process by requesting multiple keys at a time. I think keeping that below 20 keys helps keep the keyservers happy. Sort + uniq eliminates duplicate requests of the same key.

You cannot run parallel processes as your local gpg instance cannot do concurrent updates to the keyring.