The challenge with pseudonymous keys isn't only about anonymity; there is the additional problem of your identity being non-unique and harder to prove. Considering your pseudonym/nickname as established (that is, you are using an existing identity, rather than making up a new identity based on a hash or something among these lines), your nickname alone is not enough in asserting your identity and reputation.
If your nickname is Sam, if your friend's nickname is Sam, and if both of you have a "trusted" pseudonymous key, then neither of you can shout at the other and tell him, "hey, you're not the real Sam!"
One solution would be to regroup all information about your online identities in some unique place (where you tell "I am Sam on StackExchange", "I own the
samlanning.com domain and website", and so on), and then get several people to verify and confirm all these identities. I can think of two ways of doing that:
Join a website such as Keybase (or make/host your own), which does exactly what I described, and is based on OpenPGP. Although internal, all those "central unique identities" make a web of trust, for identities/pseudonyms. A profile looks like this (yes, even the main author of GnuPG uses this website).
Using OpenPGP (and especially GnuPG), find people who are willing to sign (certify) pseudonymous keys, comply with their personal way of verifying your pseudonymous identity, and request them to incorporate policy URLs and notation data in their certifications.
I personally do this when I certify other people's keys:
gpg --ask-cert-level \
--cert-policy-url http://diti.me/pgp/\#policy \
--cert-notation CD42FF00@diti.me=http://diti.me/pgp/certs/%f.notes.asc \
A policy URL is an URL (here, Internet document) inside of which you describe to the world what your OpenPGP key certification policy is. The person signing your pseudonymous key should tell (in this document) that they actually certify pseudonymous keys, and how.
A key notation is arbitrary text of the form
key=value. The OpenPGP specification doesn't actually specify what uses should implementations make of these, but one use for them is to put an URL as the
value. But you may simply have the signer put some text like "I carefully checked Sam's pseudonymous identity" if you want.
Using my command above, you can see that, on keyservers, both policy URLs and notation data are displayed by default:
sig sig1 CD42FF00 2014-04-07 __________ __________ 
Policy URL: http://diti.me/pgp/#policy
Notation data: CD42FF00@diti.me http://diti.me/pgp/certs/A31D4F81EF4EBD07B456FA04D2BB0D0165D0FD58.notes.asc
For the record, this is me signing CAcert.org's automated GPG signing key, and I'll leave here a Web Archive link to the notation data.
For as long as the notation data produced by the signer can be read, anyone can/may decide whether or not they trust your pseudonymous identity. Using these, any motivated person willing to carefully check how reputable and trustable your pseudonym is, can actually do so.
EDIT: Actually, I think I might have gone a little off-topic in point 2. Is your question only about the pseudonymous certification process, or also its auditing?