It really depends what the exchange is doing. The nature of the BTC exchanges is to received deposits and manage funds. The exchange houses you are thinking of do not do the same thing, it is just a walk in and out exchange. Taking deposits is regulated, not as a bank, but as a financial institution (same applies to all sorts of bodies that handle financial transactions).
I know several companies providing financial services, NOT being regulated, and successfully getting around that by: instead of customers making deposits, customers are "buy" "points" (for example at an exchange rate 1 cent = 1 point) and those points sit in customers account, and when the customer wants to withdraw, he is "selling" those points. These are quite large companies in Poland operating this way, providing online auction services, social lending, etc. All of them use the legal trick with "points", instead of simply deposits in currency. And it works, authorities are not touching them.