We've had an excellent experience with http://cloudinary.com/ for pretty much what you describe.
relocated a developer to spent some hours writing a restful services, now paying ~$0.030 per GB
I don't have any experience with cloudinary, but to be fair, their pricing table mentions each plan's limitations pretty clearly. Is it really their fault that you underestimated the customer's requirements?