Outlook – What diagnosis steps can I do if the emails send, but are not received, not even as spam

I have a problem where all emails to certain recipients send but never arrive, not even as spam, with no errors, while emails to everyone else work fine. I'm stumped and am looking for ways to diagnose what is happening.

• I sent some emails to a client last week, from Outlook 2016. I've now found that they were never received. I've tried emailing others on their domain and it looks like none of them receive my emails, but others on other domains do
• I've checked my "sent" folder, and they appear identical to all other sent mail. I had no delivery reports or anything similar, and they're in the "sent" folder not "outbox". I've also tried CCing myself in my latest emails to these people – they definitely send.
• I've checked with the client in question, and they never received anything from me, not even in a spam folder. I can receive emails from them, but they receive nothing from me – not even my replies to their emails.
• The first email had two small (500kb) PDF attachments, but the same fate befell follow-up emails that had no attachments. No images or links in any emails. They were normal work-related emails to between one and three individuals who I've had email exchanges with in the past through the same email address and Outlook. They're also in same country as me.
• There were no delivery error replies or anything similar. The first such email was sent 8:55am last Friday, so over 5 days ago, and nothing has been received on my side or theirs.
• Their emails to me arrive fine – and in fact, my first emails to them which failed were replies to their own emails. I've also had emails to this domain received normally as recently as two weeks ago.

• I've tried a variety of test emails to this domain and nothing goes through:

  • Innocent emails that simply say "This is a test email" and similar never arrive
  • Emails from Webmail and my Android mail app don't arrive same as emails from Outlook (and also don't give delivery reports – everything fails silently)
  • Emails sent using my phone's 3G suffer the same fate as emails sent using my WiFi
  • I also created a new email account on the same domain (for example test@my-domain.com to go alongside my usual my-name@my-domain.com), and it had exactly the same problem (tested using webmail).
  • To test if I might have some kind of messed up SMTP settings that block bounceback delivery reciepts, I sent an email to hg1ugtvr34vrgfrt2t@ashfrlwejbtlwerhtklhejtkghwerkbjhrw.com reasoning that it probably doesn't exist. I recieved a perfectly normal "Mail delivery failed: returning message to sender" bounceback – so I am able to receive bouncebacks, I'm just not being sent them from this domain for some reason.
  • Emails to them from, for example, my personal Gmail account, are received fine (so I'm using this in the meantime until this problem is resolved)

The email is from my own domain – I've sent emails to other people from the same email address and the same Outlook and they received fine. Gmail occasionally marks them as spam, which I'm looking into, but other clients seem to have no problems.

Apart from that, I can't see anything to go on. I'm sure there's not enough here to diagnose my problem so I'm asking not for a solution, but for diagnosis steps I can take, for example:

• Is there anything "under the hood" I can look at in Outlook, like a sending report or log?
• Are there any types of server or domain-related logs I should look at which might be relevant? My domain is assigned to an SMTP server on a Centos VPS.
• Are there any types of blacklist or security intervention I should know about and check for that would cause an email to not even get as far as a spam folder?

I've seen this question Emails not being received by some people, which is similar but with two differences:

• They're using a mass-mailing system, I'm using regular Outlook, one email at a time.
• The accepted answer blames greylisting – however, my first missing email was from last Friday (five days ago), and apparently greylisting delays emails for between 15 minutes and "a few days".

As Tyson suggested, I've tried http://mxtoolbox.com/ but unfortunately it didn't give any clues (at least, not any clues I can see). In case I missed something, here are the results:

Blacklist check

Checking XX.XX.XX.XX against 95 known blacklists…

Listed 0 times with 1 timeouts

[lots of green ticks then at the end of the list:]

TIMEOUT IPrange RBL Project [response time:] 0

So it's not in any known blacklists. I don't know why the IPrange RBL check failed, but I checked manually at http://iprange.net/rbl/lookup/ and I'm not blacklisted there, either.

SMTP check:

So the connection time is a bit slow (I'm not sure why, will look into that), but I don't see why that would cause sent mails to sometimes disappear completely.

http://intodns.com also give solid green ticks for all my domain's MX checks.

I've tried browsing log files on the (Centos/Linux) server:

• /var/log/maillog – these are all empty. I believe these are sendmail logs, and I don't currently use sendmail, so this makes sense.
• /var/log/exim/reject.log is full of rejected brute force attempts on dovecot. I have fail2ban and I'll get on to checking my firewall settings etc to see if I can stop them even trying, but I don't think this is related
• /var/log/exim/main.log also contains many rejected brute force attempts, but also contains records of some actual sent emails:

Here's an email to three people on the same domain that failed for all three people (I've edited some of the alphanumeric strings and replaced the IP addresses with TXT.LIKE.TH.IS):

2016-02-12 08:55:41 no host name found for IP address MY.PC'S.IP.ADR
2016-02-12 08:55:49 1aU9Vw-0004vq-EG <= me@my-domain.com H=(MyPCName) [MY.PC'S.IP.ADR] P=esmtpa A=dovecot_login:me@my-domain.com S=1443429 id=000001d17563$920b5cf0$7b1622d0$@my-domain.com
2016-02-12 08:55:51 1aU9Vw-0004vq-EG => alice.domain@receives-nothing.org <alice.domain@receives-nothing.org> R=dnslookup T=remote_smtp H=cluster5.us.messagelabs.com [US.IP.ADR.ESS] X=UNKNOWN:DHE-RSA-AES256-GCM-SHA384:256
2016-02-12 08:55:51 1aU9Vw-0004vq-EG -> brian.domain@receives-nothing.org <bob.domain@receives-nothing.org> R=dnslookup T=remote_smtp H=cluster5.us.messagelabs.com [US.IP.ADR.ESS] X=UNKNOWN:DHE-RSA-AES256-GCM-SHA384:256
2016-02-12 08:55:51 1aU9Vw-0004vq-EG -> carol.domain@receives-nothing.org <carol.domain@receives-nothing.org> R=dnslookup T=remote_smtp H=cluster5.us.messagelabs.com [US.IP.ADR.ESS] X=UNKNOWN:DHE-RSA-AES256-GCM-SHA384:256
2016-02-12 08:55:51 1aU9Vw-0004vq-EG Completed

Here's an email to one person that succeeded (was received by the recipient):

2016-02-12 08:58:20 no host name found for IP address MY.PC'S.IP.ADR
2016-02-12 08:58:23 1aU9YU-0004w0-IN <= me@my-domain.com H=(MyPCName) [MY.PC'S.IP.ADR] P=esmtpa A=dovecot_login:me@my-domain.com S=23133 id=003101d61537$874b04a0$59e01ed0$@my-domain.com
2016-02-12 08:58:26 1aU9YU-0004w0-IN => zak.receives@email-normally.org <zak.receives@email-normally.org> R=dnslookup T=remote_smtp H=cluster4.eu.messagelabs.com [UK.IP.ADR.ESS] X=UNKNOWN:DHE-RSA-AES256-GCM-SHA384:256
2016-02-12 08:58:26 1aU9YU-0004w0-IN Completed

I can't see any significant differences between the two. Before and after both is nothing but brute force debris and other emails.

I don't know what the significance of cluster5.us.messagelabs.com or cluster4.eu.messagelabs.com is, but the associated IP addresses are both MessageLabs IP addresses.

Googling messagelabs.com has turned up this blog article, which looks relevant and suggests that (co-incidentally) both my clients are MessageLabs subscribers, but for the important differences that a) unlike the author I don't even get a non-delivery receipt and b) if it was MessageLabs blocking my email, I don't see why they'd block it for one of their customers but not another.