Yes, undererandcompany.com needs to flush their DNS.
I just ran a report on your DNS.
Your SOA record [TTL=86400] is:
Primary nameserver: ns2527.hostgator.com.
Hostmaster E-mail address: root.gator1264.hostgator.com.
Serial #: 2012012401
Default TTL: 86400
These are very high refresh and expiry values. I try and get the Refresh, and TTL to 3600 (one hour) at most. The expiry value computes to almost 6 weeks.
Your MX record lives for 4 hours (TTL 14400) which I would reduce as well.
While these values are high, The domain should not be still propagating.
I believe that if undererandcompany.com flushes the DNS all should be good. They need to flush both their exchange server and the AD servers (they handle DNS for Exchange).