All users of Google search are non-paying, yet competitors have found them remarkably difficult to dislodge.

And in the other direction, Gmail is a big popular email service now, but it took many years, and a dramatic value proposition (1GB for free!) for them to make inroads against Hotmail and Yahoo.

I see no reason to believe that free users would be any less likely to be loyal than paying users.