I feel like the MIT PGP Public Key Server has been glitchy for a while-- I often get a timeout half the time when I try to do a search. Does it work reliably for y'all?
https://pgp.mit.edu/