Tracing email that "never arrived" is an administrative nightmare.
I would start (and end) by looking at your mail logs as you've already done: these will show the server your system handed the message off to, and if it was successfully handed off (no errors in your mail log) it's pretty well out of your hands, unless you want to be supremely generous and start calling mail admins at other sites.
(ProTip: DON'T bother calling unless there is a "mutually business-critical" relationship here, in which case your boss should talk to their boss to get you both together to troubleshoot the problem.).
Back when I was dealing with shared hosting/email services I used to give people this standard boilerplate when email "never got there" but our server wasn't given a good reason (we had an error-free handoff):
Electronic mail is a fundamentally unreliable service based entirely on a
"best effort" to get messages to their destination. It relies on the
cooperation of every machine that message passes through along the way,
and can fail for any number of reasons, or no reason at all.
There is no guarantee of delivery with electronic mail.
[COMPANY] has given the delivery of your message our best effort:
It was handed off from our server ([OUR_SERVERNAME]) to the server
responsible for [RECIPIENT]'s email ([RCPT_SERVERNAME]) at [TIME].
Unfortunately while [OUR_SERVERNAME] went to great lengths to move
your message in a timely fashion and ensure [RECIPIENT] would get it
we can't vouch for how much effort [RCPT_SERVERNAME] was willing to
undertake.
(I assume our front-line support staff cleaned that up to be a bit less obnoxious before sending it to the customer since I was never fired for the above -- I did get some chuckles from the new support folks though :-)