What is the safest medium on which to store my wallet/private keys?
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.