The "one way" connection for bitcoin credits won't work well if the customer has to climb 5 floors to the roof to deposit money, then go back down to the basement to retrieve the product. In other words: if the customer has Internet access, so should the machine.
I think physical tokens will always be problematic for "bitcoin" vending machines. For example, the casascius coins can never be fully validated until they are opened up to make sure the private key matches the public key fragment listed on the face.
If I have to use a token issued by a cetral authority, what not just use government-issue coinage? One difficulty may be that governments change the shape and composition of their coins over the years, so you can keep better track of changes in the tokens you are using with privately-issued tokens. I have had a self-serve check-out reject a penny two or three times, then register it as a dime!
Well the article in the OP deals w/ physical tokens. Is casino can trust those machines to validate $500 tokens then I think they could be trusted to validate 0.25 BTC pieces. Still I am not really interested in physical tokens. Eventually 3G access will continue to improve. If someone standardized it would be possible to pay via smartphone generated QR code private keys. Say keep a dozen or so 1 BTC addresses to pay someone (or some machine) "offline". They just scan the private key to import it, validate it against the block chain and then immediately make a transfer to a "secure" address they control.