After Googling, I think the key is these are "demand deposits", i.e. the firm agrees to pay the account holder when demanded. Usually other investments that pay an interest (bonds, loans, preference shares, etc.) have some capital risk or illiquidity. I'm not a lawyer & this is probably the danger of doing your own legal research, as I would have expected Paypal to immediately fall under this category.
The exchanges would probably argue that they are not deposit holders - they don't want to be classified as such because the licensing requirements are onerous and expensive. They're not merely escrow services either, because users do keep balances with them for future transactions - that's the reason why PayPal had to become an authorised deposit taking institution in some jurisdictions and was unable to successfully argue that it was just an escrow service or money transmitter (both of which have lesser regulatory requirements) in those places even though it's regulated mostly as a money transmitter and payment intermediary in the US.
The exchanges offering interest would bring them closer to acting more like financial institutions and in some jurisdictions that's going to create problems that they don't want - no matter what they call themselves, regulators will look at what they're actually doing and whether that activity is subject to licensing and regulation. I recall someone posting an answer from one of the UK regulators which specifically addressed the issue of what things UK regulators would look at in deciding what kind of licensing might be required for exchanges.
Another issue is whether the exchanges want people using them as online wallets - something which the payment of interest would encourage. MtGox has said in the past that they don't. I doubt that any of the exchanges want to open themselves up to liability if funds or Bitcoin go missing en masse when their ability to insure against such a possibility is limited.