How long will an MX record and A record change take when DNS server is not being changed?

Solution 1:

Every DNS resource record is cached; whether the DNS server itself is moving or not is immaterial. As Yahia said, how long the record is cached is determined by the TTL of the record. Before performing a DNS change, it is common practice to lower the TTL from it's regular value (a day or more, typically) down to something really small, like 5 minutes.

Complicating this procedure is the fact that some badly-behaved dns caching resolvers ignore the specified TTL and substitute their own values. (The people running these systems need to die in a fire, and if I ever get elected Grand overlord of The Internet, they will). As such, if it's an important system or one used by people outside your direct control, you would be well advised to setup DNAT rules on the system being migrated away from to redirect traffic that does get sent to the previous IP address to the new one.

Solution 2:

Do you already know the new IP address? If so, you're in luck! Setup a new A record, subdomain for your domain, pointing to the new IP, then add that as an extra MX record; set the priority higher on the new one than the old MX record. Do this a couple of days before the new IP is supposed to be activated. After the new IP address is active, remove the old MX record, leaving the new MX record. Remember to update your SOA serial each time you make edits.

Here's an article outlining failover/backup MX records: http://www.zytrax.com/books/dns/ch9/mail.html

Solution 3:

The most important setting in you senario is TTL of the respective DNS records.

The lower the TTL is set the better - you usually won't get to "instantaneous" because of all the DNS servers out there which have diverse caching behaviours but the lower TTL is set the better your results will be...