Problems with email after getting onto our own network and off of an existing network

Before the beginning of this month, we were piggybacking off of another companies network that controlled everything for us including Active Directory.  Being that we were using them to host our emails, all of our information was on their servers.  I recently got us off their network and onto our own domain, completely separate from the other companies network.

We have an outside vendor providing email services for us and everything seems to be working for the most part.  There are a couple of companies that cannot email us. I had someone forward me the bounce back message they were receiving to my personal email address.  I noticed that it was trying to send the email to the mx record for the previous companies server instead of  our new mx record.

I have had the previous company remove all information of ours from their network but we are still running into problems.  What do I need to do to have our updated mx record recognized by companies that obviously have the old mx record information cached somewhere?
Who is Participating?
emarchionConnect With a Mentor Author Commented:
This ended up being a problem on the old server.  All of the records weren't cleared out properly.  they had to contact Microsoft and have them clear the problem up for us.  I'm not sure what they did to clear up the problem.
You've got the check we're the mx-record for your domain is hosted. You kan check this by using nslookup, look for the NS record for your domain. Then check for the RP of this host/domain and contact him to modify the record.
Rommel SultanCommented:
This could happen if the TTL settings of the outside DNS server are set too high.
 and still holding the old records. Once thier DNS updates it should fix that issue.
Just give it a week to make sure that other DNS servers are updated.
It seems like they change it all at the same time.
they should change the DNS week ahead.
emarchionAuthor Commented:
The mx record for our domain is hosted at our outside vendor that provides pop3 email access for our company.  We are receiving emails from almost everyone but there is one major company that email us and the company that used to host our email that we cannot receive emails from.  Is there any way to manually update their dns to get the new records?
emarchionAuthor Commented:
The reason I am accepting my own comment as the solution is that the suggestions that were given to me were partially correct but Microsoft ended up having to help our former company out to clear up the problem.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.