Pandora? They are in a very competitive industry but they were sticky enough that most people didn't go to a competitor.

Also Hot or Not. They started as a free dating experiment but when they were overrun by spammers they switched to a paid model. Membership was still free.

I don't know if any of that's relevant to you. These are "freemiums." I can't think of any examples off the top of my head on a completely free to paid. Maybe the lesson there is you need to keep something free?