Incoming Mail Issues / Error 550 - MX records inaccessible

[PTS]

We're having some issues getting mail to come through from certain external networks.

One of our vendors is getting this error when trying to email us:

Action: failed
Status: 5.5.0
Diagnostic-Code: smtp;550 MX records inaccessible for too long for domain: ourdomain.com - psmtp

Additionally, we can't get email sent to us from yahoo.com accounts. This error pops up:

Sorry, we were unable to deliver your message to the following address.

<[email protected]>:
No MX or A records for senecagames.com