If we assume that a well-known network accessible resource Y is established as being under Bob's control, and that Mary knows of Y. What machine readable information can be be made available at Y, such that Mary can establish that the private key of ADDRESS is also controlled by the controller of Y?
Be careful here.
Signing using a private key does not indicate sole control.
It may not indicate full control either.
I could hold my neighbour's key and perform tasks for him (imagine he's not very computer focused, for example).
If you establish that Bob actually does what he says he does (e.g. Bob says 'this key is under my sole control), you can move forward.
That's a social construct, not a technological one.
Now;
'well-known network accessible resource Y is established as being under Bob's control'.
You need authentication, it's paramount, it can't be swept away as a side concern.
If you have a secure channel to Y and it's authed, Bob can send his address over it. He wouldn't send you an address that he couldn't access, that would be silly of him.
If you don't have a secure channel to Y, you need a way of Bob authenticating. E.g. PGP key or similar; Bob signs an address.
The channel could be censored but only Bob can send signed addresses over it.
This is kind of Crypto 101, I'm not familiar with all of the terminology. The basic minimum is to establish an identity for Bob. Asymmetric key seems like the best approach.