Tarsnap started out in free beta before moving to paid beta -- but this isn't quite what you mean, since at that point it was still a private beta (tarsnap became publicly available the month after it moved to paid beta).

I think as long as you make it clear from the start that your site isn't going to be free forever, you won't get any significant customer backlash -- simply because those people who would provide said backlash wouldn't sign up in the first place. Whether this is an effective business strategy is an open question, but it certainly seems like the most honest approach.