How often should encryption keys be backed up? Should this be done on the same schedule as the encrypted content/configuration? That seems excessive, as the keys do not change as often. Perhaps ...
A "soon to enter beta" online backup service, Bitcasa, claims to have both de-duplication (you don't backup something already in the cloud) and client side encryption. ...