What other legal requirements are there and what are the costs of compliance?
Yes - FinCen released details about this within the past month stating that Bitcoin "exchanger" must comply with regulations. Note that this may apply not just to exchange "houses", but also to individuals who exchange Bitcoin for USD. From the FinCen summary:
A user of virtual currency is not an MSB (money services business) under FinCEN's regulations and therefore is not subject to MSB registration, reporting, and recordkeeping regulations. However, an administrator or exchanger is an MSB under FinCEN's regulations, specifically, a money transmitter, unless a limitation to or exemption from the definition applies to the person. An administrator or exchanger is not a provider or seller of prepaid access, or a dealer in foreign exchange, under FinCEN's regulations.