If I have phone, email, fax for customer leads whats the most effective way to pursuade them to sign up to a free trial of a subscription based service.
Also the service provides more value to end users as more people sign up (chicken egg problem similar to social networks)
How did you get this data in the first place ?
Did you buy it ? Did they sign up with you for something else ?
If the first then you're out of luck, you will have to use something borderline or even illegal if you wish to use that data, depending on where you live. Especially email is fraught with danger. If you really insist in that case on doing it I would take it very slowly, and approach a couple of them (say 5 or 10) on a personal level, email from your real publicly visible email address, asking them that exact same question, and then use the feedback to formulate a strategy.
If they are already in an existing relationship for another product then you might consider sending out an email about the other service, where you can legitimately email them, and add a line or two about your new offering at the bottom.
It's a tricky thing you are trying to do here. The best method of all would be to try to figure out where these people hang out as a group and market to that channel. That will cost you but it doesn't have a 'bad taste' associated with it.
Good luck, let us know how it worked out!, It's a problem that more people are trying to deal with here.