User error is an opportunity for support to blackmail, a practice that most exchanges use.
The exchange has to access the private keys, which is not trivial. They have real expenses in attempting to recover the tokens. $500 might be excessive and there should be an option to pay out of the tokens being recovered.
Most, if not all exchanges will change a significant fee to try to recover tokens/altcoins sent to the wrong address type.
Not a coding expert here, but I think accessing the OP's account wallet with a privatekey won't interfere with the exchange's transaction log itself because it's a different network and obviously this exchange doesn't support it. It's just that some of the support is bureaucratic or has weak technical knowledge making this kind of case seem difficult to solve.
By the way they accepted to take the handling fee from the tokens to send back.