In general, it seems to me that anonymity server operators are the ones in the best position to create fake keys for nyms.
They are certainly in the best position for good or for ill.
Eric's suggestion that operators should sign the keys doesn't help much in this situation.
If the servers, however, don't sign keys, I don't think the pseudonym can prove to a third party that alteration has taken place. See the protocol below, which detects signatures on false keys.
I'd say that other methods are needed to confirm that encrypted messages to nyms are not being read en route.
Here is such an "other method." If a provider of any sort is the sole means of access to a series of communications, there will be the possibility of tampering. If some public key must issue forth through this channel only, it is possible to alter the pseudonym's public key each time it is passed throught that channel. Since every protocol which uses communications only through the server won't work, every solution needs another channel. Let us assume that the server is signing pseudonym keys. We want a protocol to detect key alteration. If keys are being spoofed, the pseudonym will have to be provided with a certificate which signs the true key, but which the provider has transmitted only to the pseudonym; everyone else sees the provider's false key. Assume a third party cooperating with the pseudonym. The pseudonym sends their own public key as signed by the server--i.e. the certificate the pseudonym has--to the third party both both through the provider's pseudonym server and through an anonymous remailer. If the server is spoofing keys, the key that passes through the server will be altered. The message contains a random number used as an ID to match up the two messages. The third party encrypts the message received from the server with the public key received anonymously and sends it back to the pseudonym, again through the server. The server cannot decrypt this message, since it is encrypted with the true pseudonym public key, not the false one. The pseudonym then checks that the certificates match. The key to this protocol (and there are plenty similar) is that the public pseudonym key is transmitted to the outside world by a different channel than the server. That's a necessary part of any solution. Note that this protocol can be completely automated. The third party could be another server which pairs up messages and sends them back. Why not just send the pseudonym's certificate with an anonymous remailer? The reason is that, assuming that all communications to the pseudonym do pass through the server, the pseudonym might never find out that their own key had been compromised. The protocol above, while more complicated, notifies the pseudonym first of any alteration. Eric