Whether the server is running IIS or Apache shouldn't make any difference, as your issue stems from the mail server on the machine being incorrectly configured and NOT from the web server's ability to send out mail from the site.
For example. If you were to signup for one of our (Blacknight) linux hosting plans the system would automatically assume that mail was being handled on there as well and would modify exim accordingly. HOWEVER it takes about ten seconds to remove the exim (mail server) configuration and send the mail externally.
If nameservers are not authorative (excuse the spelling) for a domain and are not going to be then they should not have records for a domain. Conflicting
DNS records break things.
It's not as much of an issue when you are dealing with a small provider, but if we were to put in
DNS records for something like gmail.com it would break mail for a lot of people whose mail passes through our systems... You can see where that could lead
If the hosting provider's technical support can't understand how to set things up for you correctly then you should consider changing provider. What you are trying to do is not complicated and they should be able to "make it happen"