I feel like a smart enough wallet client could solve this problem entirely, using many of the above suggestions -- most importantly crypto
I'm a dev... I'll think on whether or not I could make something that works for this purpose.
If you embed this feature into a wallet client, that means the feature is only available to a portion of bitcoin users, which is a limit...
I think the intent is to be able to add this functionality to any wallet (the wallet could confirm the address you're adding goes to the correct person), and users of wallets that don't support this functionality natively can just use a standalone program or web interface