To get a feel for how folks in the cloud are tackling security and key management, I found this AWS security talk by Bill Shinn interesting.

Some items discussed:

• Limited Blast Radius. Contain the damage caused by the loss of a single key.
• Key Hierarchies. Symmetric Key + Master Key -> Encrypted Data Key. You store the encrypted data key with the data. That key is encrypted with a master key that is stored elsewhere. How to protect the master key? Well, you could have an Application Key ... encrypted with a Server Key ... encrypted with a Region Key ... encrypted with an Availability Zone Key, say. That is, design your own key hierarchy - with the goal of reducing the blast radius of the loss of a single key.
• Auditing. Log key management activity and security-related events to one or more external agents (e.g. via syslog). Important when investigating a breach.

Update: See also Re: Security techniques every programmer should know (Security References)