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?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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:
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.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
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.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.