The problem with Monero's ring signatures in this situation is an exchange can notice that one of the pubkeys in your ring signature comes from a "stolen" coin and tell you to resubmit the tx with that pubkey left out of the signature.
What really solves this thoroughly is Zerocash, where essentially the "ring signature set" is all unspent Zerocash, and you can't leave any coins out of that set.
And hes right of course. But what if there was a way to prevent transaction authors from being able to chose which mixin partners they used. So for an extremely rough example of the idea. Certainly not saying we should do this, just to demonstrate the principal in a very abstract form. What if for a given transaction to be considered valid you had to hash the destination address + the block header of the previous block and then select the mixin partners that are numerically closest to that hash in terms of absolute value. That way transaction authors would have no choice in who their partners were. This would completely solve the fungibility concerns.
Again im not saying, HEY LETS GO DO THIS, i just want to get the gears turning in peoples heads. maybe be inspiration for some idea that is similar in some way but better.