Question : Changed MX record and now getting various SMTP delivery errors

I changed our MX record last night at 8:00pm from mydomain.com to mail.mydomain.com.  It took about 5 hours before we started receiving email again.  We aren't receiving email from all sources yet.  I'm assuming this is because it takes a while for all the Internet servers providing DNS to propagate and update.  I've just never had it take this long.  Any recommendations on speeding this up?

I also had a user get a NDR withe the following:
There was a SMTP communication problem with the recipient's email server.  Please contact your system administrator.
            4.00-012.va1-mx63.stngva01.us.mxservers.net]: Transaction (Mode: normal)>

Can anyone shed light on what is causing delivery failure on our end?  I only have one server so front-end or back-end servers.

Answer : Changed MX record and now getting various SMTP delivery errors

@1: Not exactly, with every DNS record there is an explicit of implicit Time to Live, ==> the time that another DNS can cache the answer and dosn't need to ask for a new one...
(default is 24 hours for most setups)
By preparing the move of MX and set it to 5 minutes a few days early, you can modify the record and be cutover in 5 minutes, after everything works again, you can restore the original TTL again.

So the delay is from others NOT ASKING for new the new MX record until the records expires from their caches.

@2: I would assume that stems from attempting to communicate to the OLD server, which presumably was turned off or now rejects mail for the domain.  All systems that haven't asked for the new DNS MX record yet are still trying to deliver to the old address.......