Configure proper DNS records for separate web host and e-mail server

[Frankly, you have so much pretend data here that this is probably going to be unnecessarily confusing. I'll try to keep everything straight.]

If I understand your question correctly, you currently have the following DNS records:

example.com.      A   1.2.3.4
example.com.      MX  10 example.com.
www.example.com.  A   4.5.6.7

...and a bunch of unspecified CNAME records. Also, there exists:

some.other.host.  A   2.3.4.5

...hosting your new website.

You want example.com (and presumably www.example.com) to point to your new site without disrupting email.

Try this:

• Register mx.example.com as a new A record pointing to 1.2.3.4. Update the MX record for example.com to point to mx.example.com. At this point, you'll have:

  example.com.      A   1.2.3.4
  mx.example.com    A   1.2.3.4
  example.com.      MX  10 mx.example.com.
  www.example.com.  A   4.5.6.7
  

• Now wait at least twice the TTL for your records to make sure the old MX record has time to expire from DNS caches.

• Next, update the A record for example.com and www.example.com to point to your new site. You'll end up with something along the lines of:

  example.com.      A   2.3.4.5
  example.com.      MX  10 mx.example.com.
  mx.example.com.   A   1.2.3.4
  www.example.com.  A   2.3.4.5
  

At this point, I think you have what you want. Email continues to be handled by your existing mail server, but your web presence has been moved onto your new host.

On separate domain/DNS, web, and e-mail providers:

It is not necessarily a bad thing to have your DNS, web hosting, and e-mail hosted by three different entities. There are good reasons for this:

• Separating your domain registration and DNS services from your web hosting provider ensures that your web host won't have an incentive to make it difficult for you to switch providers.
• Specialized e-mail offerings like Google Apps and Office 365 are far superior to the e-mail accounts that are bundled with web hosting accounts.

On whether a shared IP address will work for your web site:

• The web site does not need to be on a dedicated IP address.
• However, if the web site's IP address is shared with other sites, the web server must support name-based virtual hosts.
• I would suggest configuring your VirtualHost with ServerName www.example.com and ServerAlias example.com *.example.com.
• This can and should be tested prior to the actual cutover by configuring a new A record for www2.example.com and pointing it to the IP address of the new web site.

I would suggest doing the following:

• Modify the A record for www.example.com so that it points to the IP address of your current web host.
• Create an A record pointing mail.example.com to your inbound e-mail (SMTP) server.
• Create an MX record directing inbound mail to mail.example.com
• Create a TXT record containing the correct SPF information for your outbound mail.
• If you are administering your own mail server (but please don't unless you're a mail expert), be sure that the owner of its IP address has created a PTR record so that reverse lookups will identify this address as mail.example.com. This is not configured in the same place where you create your A records and MX records, and it is highly unlikely that you have the power to do this yourself.

A week or two later, once you are sure that your new MX record has taken effect, you can do the following so that people who try to visit your web site via example.com instead of www.example.com are not disappointed:

• Modify the A record for example.com (also known as @.example.com) and point it to the IP address of the new web server.

Very important caveats for DNS changes:

• If you are making changes to your web site's DNS records, your old web site needs either to remain online (if static) or forward-proxy requests to your new site (if dynamic) at least until the TTL of your old DNS records has elapsed. Do not make the mistake of pulling the plug on your old site immediately after changing your DNS settings to direct visitors to your new site.
• Similarly, if your inbound e-mail server is changing, you need either to set up an SMTP proxy at your old e-mail server's IP address or expect that some e-mail may not be delivered correctly until the TTL of the old MX record and/or up to 48 hours have elapsed.
• Naturally, these effects can be mitigated to some extent by reducing the TTL of the "old" DNS records to something relatively short (e.g. 7200 seconds == 2 hours) and then waiting until the previous TTL has expired before making any changes.

TL;DR

Create an A record that points mail.example.com to the IP address of your internally hosted email server. Change your MX record to point to the A record of the mail server.

Change the A record for @.example.com to point to the IP of the server with the new website. Create a CNAME for www.example.com that points to @.example.com. Or you can create another A record that points www.example.com to the new web server.

A little bit deeper

Some things that might be of interest to you:

3. 'Example.com' NEW site exists as a user (~exampledotcom) on an account with Company B.

FYI, I hope you have good redirection rules to either mask that the website is in a user directory. There's no technical problem with this, but... it seems a bit off.

If I'm understanding the current setup correctly, "they" are pointing 'example.com' to the email server address JUST so they can set the MX Record as 'example.com'. Couldn't you simply change the MX Record to the IP Address of the email server?

They aren't setting example.com's A record to the same address as the email server for any other reason than it is probably an all-in-one service that runs a web server, email server, ftp server and whatever else they use to manage the site. Yes, the A record and MX record are independent and can point to different hosts.

How do I need to arrange my name servers? Does the NEW site hosted with Company B need to be on a dedicated IP so that I can set Example.com's A Record to that?

You don't need a dedicated IP. Most web servers are set up to perform virtual host differentiation so that requests for your website are sent to the proper directory regardless of if you're sharing an IP address with dozens or hundreds of other sites.

Your NS records need to point at whoever holds your DNS entries, which in your scenario is Company A. Your registrar will hold the glue records (the record of what your name server's names are and what IP address their names resolve to), and in your case the registrar is also the DNS host.

All in all, it doesn't sound like too much of a mess. I've seen worse. =)