Offline generated paper wallets can be also seen as cold storage. You can deposit bitcoins inside from hot wallets. As long as the associated private keys of those paper wallets aren't imported to an online bitcoin client or get stolen, they remain safe cold storage.
I may be wrong, please correct me. I don't own enough bitcoins to go through all this hassle. I care a lot for the security of my computer and don't blindly click here and there or install unsafe crap from anywhere that screams at me to do so. (Consider using safer and less prominent OS than Windows...)
To understand the safest way to store coins you have to understand how coins can be stolen. The private key is the key to the coins. Anyone who has access to the private key has access to the coins. This means if some company uses all paper wallets but is careless about who has access to them it's probably not safe, and this can't be thought of as 'cold storage'.
Cold storage generally means not only are the private keys not on a computer with any Internet exposure, but they are typically locked away too, like in a safe/safe deposit box. As long as the private keys are printed on some medium (or multiple mediums) which will not typically become unreadable, the coins they protect are then thought to be in cold storage.
Note: addresses can continue receiving coins while the private keys are safely locked away in cold storage.
Thanks for your clarifications, both of you.