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?