I confirm, this is Bittrex hot wallet address. As soon as I saw it here, it looked familiar, and I have checked, and indeed some (in fact - most) of my recent withdrawals from Bittrex were sent from that address.
If you link the same Bitcoin address to another Byteball address, the old link is currently removed. We could blacklist such Bitcoin addresses altogether (i.e. if different Byteball addresses try to link to them) but this might negatively affect blockchain.info users who have constant address by default as far as I know (correct me if I'm wrong).
There can be a simple strict rule - if some address was linked more than once, just block it and have bot report it, so if a legit owner is trying to link it, he could move his coins to another address and link that one.
That will automatically rule out exchange wallets, as there always will be more than one cheater.
Yes, signed message cannot be abused easily.
This part below is mostly IMHO

Frankly speaking, I believe having only signature way of linking the Bitcoin address would be just enough. This microtracsaction method only messes things up. If user does not know how to sign, he could learn. If his wallet does not have signing capability, he can move his Bitcoins to a wallet which has that capability. This could be a good reason for someone to educate himself, and prove he really wants to have Byteball! Kind of a PoW - "proof of work", "proof of willingness", "proof of worthiness"
