I suspect that the regulation relates to the deposits being loaned to other people.  I doubt that there's any legal regulation which says you can only pay interest on deposits if your give loans to others.  My PayPal agreement specifically states that they don't pay interest on money deposited with them - although they no doubt receive interest from the financial institutions where they keep the majority of user deposits.

How would you see a BTC exchange funding interest payments to depositors?  To some extent, that's going to affect the answer to your question.