"Something that by the way monero clients should also take care of..."

Aside from using your own Monero node, and/or going through Tor, how else would this be done? Is there some clever scheme to get around this? 

 Clients should use tor and not refuse circuits, one circuit for each query, each query should be an address, never expose the public key.