Here is another way to leverage the work of others:
Look at this prepaid phone card vending machine:
http://www.onlinevending.com/catindex/items/C100-19-0.htmlSimply load it with empty paper wallets with a Bitcoin address on them, pre-printed onto standard size plastic cards.
All it requires is that you have some way to know immediately when a card is sold (for example, a sensor that notifies your server of a sale via a cellular connection). Your server automatically calculates the correct amount of BTC and sends it to the card at the time it is vended. Assumption is you know in advance the sequence of the cards so you know which one just got sold. Voila, bitcoin ATM with minimum engineering.
With even less engineering, you could activate the cards simply by pre-printing activation codes and then having the buyer use their cell phone to notify you they just bought the card by visiting a URL, scanning a QR code, or calling an activation number just like a prepaid phone card. (they end up getting the exchange rate as of the time they activate it instead of the time they buy it, but it's sixes)
How about you vend bitcoin addresses as you say for a set $ amount ie a $20 card. User retrieves card and holds card's QR code up to vending machine's scanner. $20 worth of btc then sent to the address.
edit
Oh ya. Awesome job OP.
That's essentially what I have suggested, other than that to do what you've suggested, that vending machine would have to be outfitted with a scanner, with an associated programming expense, maintenance expense, and recurring communication charges to keep that scanner in contact with home base.
There is value in simplicity, both in terms of cost to those who will use/own/operate/maintain the machines, as well as how long it would take to go from idea to fully functioning implementation.
Meanwhile, if the customer can just use his own cell phone, or go directly to the redemption URL printed on the card so he can enter his own destination bitcoin address, then the solution is that much simpler. Someone can buy a phone card vending machine TODAY and start selling bitcoin cards TODAY without hiring programmers to implement that scanner... all that is needed is some cards to sell and a web platform for redeeming the cards.
Importantly, that web platform need only be created once by one company in the business of selling cards, and then thousands of internet cafes could start selling bitcoins from a vending machine TODAY.