This article is from the PGP FAQ, by Jeff Licquia firstname.lastname@example.org with numerous contributions by others.
This problem can arise when you have placed the entire public key ring
from one of the servers into the pubring.pgp file. PGP may have to
search through several thousand keys to find the one that it is after.
The solution to this dilemma is to maintain 2 public key rings. The
first ring, the normal pubring.pgp file, should contain only those
individuals that you send messages to quite often. The second key ring
can contain ALL of the keys for those occasions when the key you need
isn't in your short ring. You will, of course, need to specify the key
file name whenever encrypting messages using keys in your secondary
key ring. Now, when encrypting or decrypting messages to individuals
in your short key ring, the process will be a LOT faster.