If I send you my public key -- even if I cc: dockmaster -- what does it matter that the NSA knows my public key (unoless they want to send me msgs, too)? The key itself is inherantly secure. Let your users decide on their public keys and register those keys with your key server. Not the other way around.
Let's make this short. The basic problem with public key systems is to make sure that what _I_ think is my public key is the same thing as what _you_ think is my public key. If these are not the same, something is wrong. At worst, an interposer is getting all your mail, decrypting with one public key and encrypting with a different one. Servers, generally, are not desirable because they are too prone to communications filters of the above sort. For a more detailed reference, read the excellent introduction to the whole topic of public key distribution in the PGP 2.0 documentation.
Course, there's always the Kandinsky-Ogorov method of key exchange.
Please elaborate. Eric