Until it has been expressly verified, external DNS errors are the principle suspect for this behavior. It's likely that the MX record, and the forward and reverse DNS translations of the mail server don't match.
Without correct DNS, then some of your inbound messages will be dropped (at the sending mail server), and some of your outbound messages can be dropped (at the receiving mail server), but mail services can generally and usually still work when interoperating with the less-aggressively-configured mail servers.
If you don't want to post your domain, then verify your DNS translations with the "dig" tool or otherwise. dig mail.example.com and dig -x ip.address.of.server and dig MX example.com, where example.com (and mail.example.com, and the IP address ip.address.of.server) are adjusted to match your domain. If you're less shy, post your domain and we can verify it.
Thanks for taking the time to respond. Unfortunately in the course of trying to investigate further with an engineer it now appears as though the server disk is in a very poor state and we're now having to replace this. I'm hoping that the disk failure is in some way responsible for the issue but all will be clear once replaced.
I'll keep the question open for now until the disk is replaced and I can verify if the original issue has also been resolved by replacing.
I'll post back soon. Thanks again, much appreciated.