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.
I don’t think it is an issue with the transaction logs, the issue is with having to actually access the private key. This is not trivial. Precautions need to be taken when accessing the private key, and this is probably not as simple as an engineer accessing the key and manually creating a transaction. Most likely, this will involve someone creating a script that gets the private key, calculates the address, checks the relevant blockchain, and creates a transaction, all without a human having access to the private key. This script, or scripts if multiple systems are involved, will need to go through testing to ensure that it is safe and does not leak any sensitive information.