I was looking for something similar a year ago
than I after trying few VPN provider, most of them have bad reputation IP wise; which is not good to send email
overall my choice stop at : https://www.goldenfrog.com
because it was possible to expose your machine directly to the net from their IP
but still you will need a dyndns service because even the IP is dedicated it still not static.