Ultimately it depends on how much the data is worth to you when it comes to assessing how much you should spend on the solution. If you want to use a cloud provider then I would also look into the commercial inline encryption appliances (e.g. SafeNet) as then you control the visibility of the data in the cloud. If you want to spend a bit less then you could look into cheaper encryption options but again storing the data offsite is a must. Have you spoken to others in your industry that are facing the same challange? If so you might find a colo opportinuty that will keep costs down and be beneficial to both organisations. Obviously you still want to ensure the Integrity and Confidentiality of the data you store at the remote location but you have offsite storage and you could possibly negotiate a better deal for a mutually beneficial agreement then from a third party. Just food for thought.

There is a lot of commentary about Google here but my concern is that Australian's seem to have gone to sleep and awoken up in China, or worse North Korea, since the last election. Howard needed to go, Abbott is not a good alternative but the Ruddinator's lackeys are going to turn us into even more of an information backwater if they continue unchecked. The policies being pushed in Australia of late are very concerning.

The article on PCM might be the answer. A digital medium that stores information by physical structural change would potentially offer much longer life however given the tech is similar to CD/DVD-RW you might be puting your eggs into a basket no better than DVD. Papyrus, tried and true for centuries.