It's completely possible. If the exchange creates a separate contract for ERC-20s for each user, they can know when that user deposits an ERC-20. They'd likely then send all the tokens to a central wallet, and keep most of it in cold storage of course.
The sad thing about the ERC-20 standard is that there's no way to trigger code on deposit of an ERC-20, e.g. yes I can send ERC-20 to the contract that the exchange created for me, but that contract can't automatically forward the tokens to another contract in the same transaction. Of course the exchange can just detect when it receives tokens and create another transaction to move the tokens. This is the main purpose of the ERC-223 standard that is in the works, allowing a tokenFallback function to execute if the receiving function is a contract and implements tokenFallback.