@mathowie One way around that might be to use a web-of-trust model. If a person has a certain threshold of contacts who all know one another mutually, it kind of enforces that this person is real.
But yes, this is one aspect of decentralization that still needs a definitive solution. Interestingly, the #Hubzilla platform worked around it by using ratings from an implementation of Portable Contacts - your profile can be rated and given feedback from people you're connected with.