Diomede might be worth a look. Their offline and nearline options are waaay less expensive than S3. Never used them though so let us know how it works out if you go with them.
Edit: Actually, it looks like they closed on Mar 19, according to an email they sent to existing users. They say they might reopen "with a new approach" near the end of the year.