I would try talking to your ISP and seeing if it's really the case that they block VPN over their network. I'm also not sure I see how blocking VPNs would prevent e-mail being sent through SMTP, unless it's something special about your network configuration and/or SMTP server you're using. Did you also set up new network equipment when you switched ISPs? Have you made sure that ports used for SMTP (typically 25 or 587) are open on your network equipment?
A free Google account would allow using their SMTP (limited to 200 recipients per email, I think)
I would check your ISP's email configuration instructions, setup is most likely to be the problem.
Many block default port 25.