I've thought a little more about it, and there's an issue with the air gapped printer idea.

If we're talking about an air gapped device, that's because we cannot trust our other devices. So, let's assume somebody has one of these printers, but all of his computers are compromised with bitcoin-stealing malware.
While he uses the printer to generate addresses, and only gives these addresses to those that should credit him, he should be safe - assuming the malware is not advanced enough to also tamper the messages where the user sends his addresses to others.

But what would this user do when he wants to spend the money he has in these safe addresses? If he loads the private key into any of his computers, he loses the money.

For such a device to be complete, it should be able to generate offline transactions as well. But that would probably require a way to scan QR-codes. Manually inputing addresses is error prone and annoying.
Anyway, this increases the complexity of what you're trying to do...


Suggestion: talk with someone42, who started this topic: https://bitcointalk.org/index.php?topic=78614.msg879194;topicseen#msg879194
He's trying to do something similar, but purely digital instead of paper printer. I tend to prefer it since I'm not a big fan of paper wallets anyway. But I guess the printing part is not the hard part.