Ask HN: Minimally-intrusive ways to verify real name?

I'm sketching out a system which would need to associate public keys with real names. What's the best way to verify that the person submitting a key is, in fact, named "John Smith" as he claims? I've seen credit cards used for this purpose, but a lot of people are understandably wary of passing out credit card numbers.

A method involving actually phoning someone up, or sending snail mail, would also work. Each user would only have to verify once, although having provisions for invalidating a previous key would also be good.

Any thoughts?