While paying for a service gives one more confidence and, if it's a large company, I'd be surprised if they just shut things down overnight, you don't really have meaningful recourse if they just go belly up or just make a really bad IT mistake. Ideally, use multiple storage locations--private and hosted.

With respect to the parent comment about Kodak, they actually transferred things to Shutterfly and photos supposedly did not just go away: http://articles.latimes.com/2012/jul/05/business/la-fi-tech-... This also wasn't really a "free" service as it was supposedly a feature you got with the camera.