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.
As far as I can tell, they're closed down ... their blog (http://diomedeblog.wordpress.com/) has been inactive for over a year, and as far as I can see there's nowhere for existing users to log in (they had open signups at one point last year...)
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.
http://www.diomedestorage.com/