The mail server, of course, needs an A record as well as an MX record. If the mail server is in some other domain, of course, the A record is supplied by that domain's DNS server.
It would probably be useful to give some details, using "example.com".
i had example.com on a mac mini in south carolina. it had web, intranet, mail, dns....etc.
i created a new site with a hosting company.
i logged into go daddy and changed the dns records to point to my new dns server, with the hosting company.
somehow, some top level domain servers kept the old IP address in their records, along with my new domain servers..
so in essence, there are top level domain servers dishing out dns records to my old and new site....
so its a good old crap shoot to see what site you get....