QR code scanner. If someone wants to deposit BTC, they transfer the BTC they want to deposit into a one-use wallet, and then print out the wallet's private key into a QR code on a piece of paper.

When you get to the machine, scan the QR code, machine verifies BTC is still on the address, and then dispenses Euros.

Problem solved?