Personally, I think that the registrar should send a verification code to the paper mailing address provided by the registrant, and not activate the domain until the registrant receives the code and shows (probably by web or email response) that he or she has received it.
I realize this would make the registration process considerably slower and somewhat more expensive, but I see no public interest reason why that's a bad thing.
I would guess that this would only need to be done for new Registrar:Registrant relationships. Once such a trust relationship is established (perhaps periodically renewable) additional registrations would not need to go through the process, thereby significantly reducing the potential impact.
So long as you were sure that it was the same person and not just someone borrowing the same contact details, I'd agree.
However, it is unclear if this could be effectively implemented in parts of the world with inadequate paper-mail capabilities.
Are there really places with Internet connectivity where you can't get a letter with one sheet of paper delivered? I realize that parcels get pilfered, but letters? R's, John