cannot send or recieve to certain domain

We have an error that started about a month ago but no changes were made in our system. We can’t recieve or send to a few domains. the error message when we send is:
” The e-mail address could not be found. Perhaps the recipient moved to a different e-mail organization, or there was a mistake in the address. Check the address and try again.
<******.****.com.au #4.1.8 smtp;451 4.1.8 Domain of sender address ****@****.com.au does not resolve>”
We have had an outside source check our dns to make suure there wasn’t something we were missing, enabled reverse dns with our isp, checked on “dns stuff” to ensure things are fine.
I guess the question is why a few and not all?
A month is too long and we have run out of options so all help is welcome.