External SMTP Server Possible?

I was having major email-deliverability problems before I started using a 3rd party smtp server. The issue I have with that is each mail client needs to be configured for that 3rd party service. I fixed the issues (DKIM, rdns,etc.) back before I even started using the 3rd party SMTP service and I can deliver from the 3rd party email service as me@mydomain.com without going to spam so I think it's just the current IP set that is blocked internally at top providers (gmail, yahoo, aol, live, etc.) from back before I made the dns changes. When I view the headers in an email that is not through the 3rd party provider, although in spam, the tests all pass with flying colors now. Is there a way I can spin up a vm and just run an SMTP server on there under a whole new ip block? I would like to config my WHM server to use this SMTP server by default to anyone using the default mail settings. If this can be on selected accounts only that would be even better. What about multiple external SMTP servers? I figure I will have 15 IPs on each of the 2-5 VMS for my clients who would like to pay for mail services. Any help, comment, opinion is appreciated! Also, I would rather not just add more IPs to the dedicated WHM server to accomplish this.