-snip-
my reasoning was that they asked for an exchange receipt and as the payment went from (binance-> my wallet -> my ole wallet),
Too complicated. If they're willing, you can once again deposit a small (unique) amount they specify from (the same) address to the address like beforw. I think that's enough to prove the ownership of the $500 you deposited previously.