It would probably have to be a centralized service, and I don't think one exists yet. It may be possible to implement that into a client and have it become a feature of Bitcoin, but that would be difficult to do decentralized.
Yes it could be a feature of the wallet, after all the only thing you are doing is holding a transaction until the new address is claimed. There is the question of what happens to those coins while is being held, can
John touch those coins? Can they be transfered to the wallet temporary address until the transaction is claimed. There are different options on how to process them.
You would have to trust that whoever generated the address (and thus privkey) that holds the coins doesn't spend them.