I'm assuming that you're receiving email directly from the Internet via an MX record that refers to your Exchange Server computer (based on your statements re: using TELNET to run SMTP "by hand"). If you have any anti-spam / anti-virus filtering in place you owe it to yourself to double / triple check this before you start complaining to third-party sysadmins.
Having said that, the best place to troubleshoot this, next, would be on the sender's end. If you can't get traction from them to monitor their outbound email flow then you could try to capture traffic on your end but it's likely you're going to have a gigantic haystack to comb through.
The senders should be looking for SMTP protocol logs or whatever their email system has equivalent to Exchange "Message Tracking" (/var/log/mail.log, etc) to find out how their server dispositioned a failing message (which the sending user should be able help them identify in their logs). Assuming they are "losing" the message, blocking by policy, etc, it's silly that their servers aren't sending an NDR back to the sending user. Black-holing outbound email is never the answer. (Sending NDRs on inbound email, arguably, may not be such a great idea. Yeah, yeah-- I know that several RFC's say you should... >sigh<)
If the senders can't help you then your only hope is, very probably, to capture traffic at your border and attempt to identify connection attempts (or the lack thereof) from their outbound server. Assuming you can get somebody to send a message on command (say, during a telephone call) and assuming their outbound server infrastructure doesn't take a long time to process the message you should be able to capture an SMTP conversation with the sender's server (or nothing, if it's never getting to you).
Truth be told this really isn't your problem, from a technical perspective. Unfortunately, users and management don't understand the "wild west" nature of Internet email and frequently see it as a reliable form of communication. When reality proves otherwise they often blame the closest email sysadmin, rather than accepting that, not unlike postal mail, it's not a reliable system.