I use constant contact, and they are about as good as it gets. You might want to check out road runner too, but I'm pretty sure constant contact is the tops for email campaigns.
I have also used a program called
OEM Pro which is awesome. You can buy this for a few hundred bucks and then you don't have to use an external server. I think they have all the features constant contact does, and if not, they at least compete.
As far as sending out emails, I think you're right, since you have had contact I don't think it violates a spam law, but I would do some research to see if there is a time limit on the contact just to make sure. As for preventing the people you send it out to deleting it or reading it and hating you, it will take some very carefully crafted text. Your message has to be professional, polished, polite, interesting, not spammy, and you have to make them feel safe and give them an opt out. Mention the fact that you had contact with them at one point and that's why you thought they may be interested in your new site. If it is really important to you, you may want hire a copywriter. I can suggest an excellent one if you need one who (and don't quote me on this) will probably write something up for you for around 250.
Good luck, use your best judgement and don't spam. :lol: