I’ve had a lot of inquiries over the past years about Bitcoin vending machines (aka ATMs). The general concern, and one of the primary reason holding back machine adoption, has been around compliance issues. For the avoidance of confusion, I’m going to refer to the devices as Bitcoin kiosks.
I should mention that this blog post should NOT be taken as legal advice. I am a lawyer but I am not your lawyer. Your fact and circumstances may dictate the application of the law you to in a different manner. This is all new territory and it is unclear how regulation will affect kiosk operators. In other words, my post here is speculative. In addition, this is not meant to be a thorough analysis but rather a quick thought on the issue and I would investigate in more detail the legal issues for a particular client.
The most typical process I see with the kiosks with which I’ve seen are you deposit some paper currency, then hold your QR code up to a camera which captures your public address, and transfers the funds to your Bitcoin address. From a FinCen perspective, the risk here is that you are transmitting funds to another person or another place. Title 31 Section 1010.0100(ff)(5) defines a money transmitter as:
(5) Money transmitter—(i) In general. (A) A person that provides money transmission services. The term “money transmission services” means the acceptance of currency, funds, or other value that substitutes for currency from one person and the transmission of currency, funds, or other value that substitutes for currency to another location or person by any means. “Any means” includes, but is not limited to, through a financial agency or institution; a Federal Reserve Bank or other facility of one or more Federal Reserve Banks, the Board of Governors of the Federal Reserve System, or both; an electronic funds transfer network; or an informal value transfer system; or…
The concern is thus that the QR code doesn’t belong to the person presenting the money at the kiosk. The person depositing the funds in Atlanta, GA could be displaying a QR code to a person in Belarus, thus employing the kiosk operator unwittingly as a money transmitter. The common response of operators is that they will employ a terms of condition forbidding such activity. Unfortunately, the U.S. government will take a dim view of that. As the business owner, the onus is on you. Forget the fact that Bitcoin facilitates its own transfer and so you’re not really providing anything they can’t do on their own, the operator will still likely be on the hook.
One avenue to ensure compliance is to identify your user. I believe Robocoin is building their machines to do facial recognition, ID verification and possibly other forms of biometrics. I’m not sure if they pre-validate the wallet. In other words, have the person sign something with their private key or initiate a transaction to prove ownership in the address to which funds will be deposited. That would be the safer course. 
Another option was on display with CoinOutlet, a kiosk operator that provides printed on the spot new addresses with both the public key and private key (see illustration at left). This certainly alleviates the concern that the person is giving the operator an existing address belonging to someone else in another place. The buyer is still free to transfer that private key or immediately transfer the funds, but that it outside of the operators control.
I’ve seen another kiosk that provides the same thing via an onscreen display. Both of these though raise a security risk to the purchaser. A QR code skimming device could be placed in the printer or a high power camera could watch the computer screen. A better option would be pre-printed Bitcoin wallets akin to what the Bitcoin Foundation gave out at the Financial Cryptography Conference in Barbados last year (see below). The public key is exposed to allow a user to get the balance of the account (and the kiosk to deposit money into it) but the private key is inside an envelope sealed with holographic tape. The user is free to take the paper wallet home and load up their electronic wallet. 
Feel free to make donations to the above public key! I haven’t unsealed my private key as of yet, keeping it more as a souvenir than the 0.01 BTC that was given to attendees.
If someone were to implement the above styled machine it would truly be more like a vending machine than an automated teller. I don’t think anybody is doing that to date but if someone is, please feel free to contact me and let me know.
Just to reiterate, this post is not meant to be a definitive legal case for how you should operate a Bitcoin kiosk but rather just suggestive of one solution to avoid a nasty and complex compliance regime.