Assigning new addresses to users after every transaction seems to be standard practice with exchanges now. I've confirmed that Shakepay and Coinbase both do this.
Using a new address for EVERY TRANSACTION is not a problem. That's actually the best way to use bitcoin. The concern is if those receiving addresses are being treated as account numbers and the funds are not being held in cold storage.
I can also confirm that these new accounts are not pooled with anyone else.
First of all, they are not "accounts". These are "addresses". There's a huge difference. A bitcoin address is more like an invoice number than an account. It's a way to track and control a specific payment that you receive.
The address that Shakepay created for me has only one incoming and outgoing transaction that matches the transaction I made.
That's a HUGE problem. If this is true, I'd avoid using Shakepay until they can demonstrate that they've improved their security practices.
I think I'll side with the FX broker on this one since it would be heaven for money launderers if they could deposit BTC from one address and then withdraw to a completely different one.
There's no such thing as depositing "from a bitcoin address". This sentence doesn't make sense. You deposit TO an address (specifically, the address that the ForEx provider tells you to deposit TO). It's entirely possible AND VERY COMMON for a single transaction to contain bitcoins that were received at multiple different addresses. Which address would the ForEx broker require you to use in that case? It's also possible for a transaction output to contain a script that can not be converted to an address at all. If you sent those bitcoins to the ForEx, how would they handle your withdrawal?
Under most circumstances, Bitcoin addresses should NOT be re-used. Once you receive bitcoins at an address, you should not receive additional bitcoins at that address in the future. You should use a new address each time. There is no money laundering benefit that is prevented by requiring someone to re-use a previous bitcoin address.