Why do I need a bitcoin wallet for cold storage? Can I just write down randomly generated public address and private key pairs, and keep these on paper? I am confused by the apparent need for a wallet stored on a thumb drive or some other data storage device that may become corrupt. So why do I need the wallet?
You can indeed just write down, or print out the private key. Strictly speaking you don't need the public key in cold storage. Paper stores well for a long time as long as it is of archive quality. I would trust that more than any magnetic storage. Paper has been around for a long time and we know how to make it durable against time if so required. The ink of the pen needs to be of archive quality (at least where I live some pens are classified as such). Leaving the paper in the bank vault leaves you with one single point of failure though. And you may have made an error while copying the key to paper.
You could make another copy and give half the key to one trusted friend or relative, and the other one to another trusted friend or relative. It would be easier to brute force half a key for one of these people, but they are hopefully not into that with your key and half a key is still a lot of work.
If you consider using an offline computer, you could enter your private key into a local off-line copy of this page: http://passguardian.com/
It implements Shamir's secret sharing and allows you to print out "keys" that needs to be combined (e.g any 3 out of 5) to yield the original key. Then give those out to people. Use a laser print for all print work, not an inkjet, since ink can be destroyed by water easily. The laser printer must not store copies of your print outs.
Laminating the paper as is suggested in another answer, then one would need to know that the plastic does not degrade the paper in the long run. There is no long term information on this, since laminated paper wasn't around 200 years ago.
Edit: Here is a link discussing archival standards at the Technical Research Institute of Sweden:
Here is a list of their approved stuff; look in the left hand column and navigate down to the desired category: http://www.sp.se/en/index/services/certprod/certprodprofil/arkiv/Sidor/default.aspx
You can indeed do this. It has multiple environmental factors though which make this a bad idea.
Paper is easily damaged and very degradable.
You could make a mistake. If you do intend to do this maybe its best to quadruple check it.
Lack of extra security - unless you have it locked away in a safety deposit back in the city undergrounds, someone who knows it is there could steal it. Data drives give you extra level of security with wallet encryption.
There are probably other reasons but these are the main three, if you do decide to just do this there are a few techniques you could use to improve these factors..
Try laminating it, will give the paper exponentially longer lifepan.
Miss out a character that only you will remember, replacing a single character of a private key is easy if you know where it goes but hard if your not you, obviously just don't forget it!