Perhaps my background in hardware systems leads me to solutions that use physics to solve certain security problems, but to me, sending bitcoins to an unconnected computer over a unidirectional link seems trivial.
User owns a key protected by his password and your server never knows it. Another key is stored unencrypted on the web server (like in "hot" wallet). Third key is stored with your staff, encrypted by their personal password (like in "cold" wallet).
Normal withdrawal: user key and web server's key sign the transaction and it's instantly available.
Security analysis:
1. User forgot their password: he contacts staff that uses their key + web server's key to move funds to new destination.
2. Hackers have taken the web server: they see the key, but it's not enough to move anyone's funds.
3. Staff lost their keys: users still can access their funds if they still remember their passwords.
4. Hackers stole user's computer: they may instantly withdraw some amount up to an arbitrary daily limit. (Withdrawal can also be protected by 2-factor authentication.)
5. Hackers stole staff's keys (e.g. from a personal computer): they still need to break into web server. When staff realizes that keys are compromised, all funds must be moved immediately to new keys.
In other words, users have a hard proof of ownership of specific coins. All coins, no exception, are protected by two differently stored keys. So no need for hot/cold wallet difference.
If you want to block some BTC for trading, webserver will implement that easily: when you withdraw coins, it will move blocked portion to someone else's address.
The transaction history, and thus the ballance of an address is held in the blockchain, in the ether.
To spend the coins, you must have at hand:
* the current blockchain
* the private key
* a connection to the network.
What is considered risky is spending only a fraction of the paper wallet, for the following reasons:
- you just used the private key for creating a transaction, so the chances of it being compromised increases
- the client you used might have sent the change to another address while you're thinking the remaining coins are still in the paper wallet
But if it's done well, yes, it's possible to spend a fraction of a paper wallet.
If I wanted to take it further, the "secure" machine could print that wallet onto paper or could robotically insert flash drives into a USB port (in such a way that removed keys were dropped into a bin the robot couldn't reach into.
This is only one of many ways I can think of that would allow the automatic creation of cold wallets ... the only way to attack such a system is to gain physical access.
TL;dr version: anything that is connected to the outside world, no matter how small, is an attack target.