I would think it is better to start with a smaller amount - not zero just to make sure you are getting users who would be willing to pay the real (higher fee) later. Subsidizing to zero only works for those which either have a network effect or ad-supported.
Studies show its at least 20 times harder to get a paid conversion than free conversion regardless of price (example being free app vs 99 cent app downloads)
I think it will be easier to convert more than 1 out of 20 from free to paid once they see the value of the search
