Changes to DNS should be relatively instantaneous on your authoritative servers. However, due to DNS cashing it will take a while for the changes to get out to clients. This will be more of a problem for frequent clients than occasional clients. You can work around this by pre-populating your data.
The various answers already posted cover everything you need to worry about.
- Set the TTL on to a low value. Say 1H a few days before the change. Try to do this at least the current TTL before the change, 2 times TTL would be better.
- Add two new A records for the mail server using the old and new addresses. Create an MX record for each of these giving highest priority to the old server address. Remove the MX for the old address as soon as you cut over. Set the priority on both these records lower than the existing record. (Sending servers shouldn't check the name your banner uses.
- Add a new A record for the mail server with its current name. And get the PTR record setup for the new address The A record will return both addresses. This will allow rDNS validation to work for either address. (Many receiving servers care about this and may refuse messages or classify them as spam if rDNS fails.)
You are now ready for the cut-over to the new address. After the cutover you can cleanup.
- Remove the MX records for the new names and the A record for the old address.
- Wait a few hours and remove the A records for the new names.
This should be completely transparent to your users. Any problems you encounter should be restricted to servers which are non-compliant with standards.
You can use the double A record technique for other services, but there will be delays when clients try the address which isn't responding and wait for it to timeout.