Have you looked at Amazon Glacier? The volumes you're storing might make this cost-prohibitive, but it's explicitly designed for long-term storage of rarely-accessed data.