While I understand you have been with them for a long time, and their support is good etc, they are unfortunately not providing the service in which you want to have provided. The issue you have is really an issue of what you are using to send your mail (currently your hosting), rather than an issue with the software.
I would say, you can already export members with their email address from the members page in your admin CP by the way.