What is the safest medium on which to store my wallet/private keys? What is the safest medium on which to store my wallet/private keys?

I avoid eWallets like the plague.

I have my wallet on my computer at the moment with the Bitcoin passphrase encryption and I have a few backups on different harddrives/USB drives.

But USB drives don't seem to be the most reliable thing to store wallets on, and I want to move my wallet off my computer for improved safety, so I was looking at paper wallets and they seem good apart from if they deteriorate over time, or from things like water damage etc.

CDs seem okay to use but they can also get scratched and can't be updated once burnt.

I'd also rather avoid cloud file services.

A plastic card that I could print my public/private keys on seemed like a good idea, but this would have to be printed by a third party as card printers are expensive, unless there's somewhere I can go to do it myself.

Any recommendations on the safest medium to store Bitcoins on?
Print out your private keys to a Paper Wallet and print the keys on Archival Quality Paper. Those should last until the year 2211. They are however un-encrypted so you should store them in a bank safety-deposit-box or somewhere just as safe.