I disagree on the CPFP part. If - say - Binance now pays 100 sat/byte for a transaction with 100 outputs, they could easily to for 10 sat/byte and still get into the next block
about 90% of the time. For the 10% they don't make it, they could instantly do CPFP onces fees in mempool go up. If they quickly bump the average fee to 25 sat/byte, they can still make it into the next block, and depending on the state of mempool, they can increase fees by as much as needed.
The cost of an incidental CPFP is tiny compared to the amount they save on total fees.
The users are paying 0.0005BTC per withdrawal. Granted that includes the fees from moving the deposits around, I would assume that the first course of action is for them to reduce the withdrawal fees for the user. Even if they decrease that they are going to use, users are going to complain that they are skimping on the fees.
How ever much they spend isn't any of our business; it affects their profit margin and screws their users over. Them adding additional TXes into the mix doesn't necessarily bode well for the rest of us, there is another transaction to compete with the rest of the network. Even if they were to pay the high fees, it doesn't necessarily affect the remainder of the user. Algorithms don't look at the average fees being paid, rather, they devise their estimates from the bulk of the fees that the network is paying through fee buckets. Having a fraction of the blocks being occupied by a few high fee-rate transactions isn't a problem for the rest of the network, as long as the bulk of the transactions are still paying a normal fee rate.
I mean they aren't wasting any money, the user foots the bill.