It seems like in addition to all that, they could offer the option for the user to set the proposed fee themself and take responsibility for the transaction from there.  The user could choose to set a low priority fee and wait; or even choose to pay an acceleration service if it ends up taking too long.

Obviously, this wouldn't be great for the less experienced users - but that's why you would only offer it as an option.  And, it would sidestep batch withdrawals and thus some potential profit for the exchange - but, the more experienced users would likely appreciate and repay that freedom with more customer loyalty than they otherwise would when they don't have the option not to get fleeced on fees.