Exchange 2003 SMTP does not receive RCPT from sender

I am mainly asking this to check whether I should be investigating further on my end, or if I should tell the sender they should talk to their own IT department for further assistance. I am not sure if this is on my end or theirs.

From one external domain, we are not receiving any emails. The only tracking I can see is an initial SMTP conversation logged on my SMTP Virtual Server. The log shows the EHLO, STARTTLS, then MAIL, and last a QUIT. There's no RCPT sent from them that I can see anywhere. I even used Network Monitor to see if there was anything in the packets, nothing showed.

We do have GFI Mail Essentials on the same Exchange server, but nothing is logged, not even any addresses from that domain in the history. In Exchange event logs, with Transport logging all on maximum, there are zero log entries with their IP's or addresses or domain. Basically, I think the mail never goes into the Exchange transport pipeline.

Also, checked, no blacklisting on our or their servers. And, DNS lookups all resolve, reverse PTR as well from my end.

We are just a small shop, a few hundred users, and not a full time IT staff, only a single Exchange server for all email. The sender is a large federal government organization with many inbound MX records and all outbound is coming from separate SMTP servers.

Currrently I am waiting to hear from my users to see if any NDR's were received on their end. I am just confused at this point, mainly since, obviously, I can see anything from their end.

Could this be on my end still? I don't know what else to do except tell them it on their end, which I hate to do. (because I hate it when other IT people do that to me without checking everything)

Thank you for any advice or suggestions.

Below is a sample SMTP log:

2014-06-27 19:07:36 52.0.222.46 outside1.domain.com SMTPSVC1 MAIL 192.168.0.4 0 EHLO - +outside1.domain.com 250 0 343 19 0 SMTP - - - -
2014-06-27 19:07:36 52.0.222.46 outside1.domain.com SMTPSVC1 MAIL 192.168.0.4 0 STARTTLS - - 220 0 0 8 0 SMTP - - - -
2014-06-27 19:07:36 52.0.222.46 outside1.domain.com SMTPSVC1 MAIL 192.168.0.4 0 STARTTLS - - 220 0 29 8 0 SMTP - - - -
2014-06-27 19:07:36 52.0.222.46 outside1.domain.com SMTPSVC1 MAIL 192.168.0.4 0 EHLO - +outside1.domain.com 250 0 353 19 0 SMTP - - - -
2014-06-27 19:07:36 52.0.222.46 outside1.domain.com SMTPSVC1 MAIL 192.168.0.4 0 MAIL - +FROM: 250 0 76 41 0 SMTP - - - -
2014-06-27 19:07:36 52.0.222.46 outside1.domain.com SMTPSVC1 MAIL 192.168.0.4 0 QUIT - outside1.domain.com 240 343 76 41 31 SMTP - - - -

2014-06-27 19:14:56 52.3.222.45 outside2.domain.com SMTPSVC1 MAIL 192.168.0.4 0 EHLO - +outside2.domain.com 250 0 343 19 0 SMTP - - - -
2014-06-27 19:14:56 52.3.222.45 outside2.domain.com SMTPSVC1 MAIL 192.168.0.4 0 STARTTLS - - 220 0 0 8 0 SMTP - - - -
2014-06-27 19:14:56 52.3.222.45 outside2.domain.com SMTPSVC1 MAIL 192.168.0.4 0 STARTTLS - - 220 0 29 8 0 SMTP - - - -
2014-06-27 19:14:56 52.3.222.45 outside2.domain.com SMTPSVC1 MAIL 192.168.0.4 0 EHLO - +outside2.domain.com 250 0 353 19 0 SMTP - - - -
2014-06-27 19:14:56 52.3.222.45 outside2.domain.com SMTPSVC1 MAIL 192.168.0.4 0 MAIL - +FROM: 250 0 76 41 0 SMTP - - - -
2014-06-27 19:14:56 52.3.222.45 outside2.domain.com SMTPSVC1 MAIL 192.168.0.4 0 QUIT - outside2.domain.com 240 516 76 41 63 SMTP - - - -

By the way, I did notice some SSL traffic in the Network Monitor where they request the STARTTLS. In that I see ClientHello from both parties, that always end in an SSL Error about authentication invalid or similar. I have a hunch this is not my problem, because its also showing on other normal traffic. I believe the servers are simply attempting TLS connection, then falling back on normal unencrypted connection. Hence the second EHLO. (right? I am just making a guess on that, I really don't get the SSL protocol stuff at that level.) I really think this is something with the lack of RCPT in the transmission, no mail will route without that.

I just don't know what else to check, is it me, or them? Won't know more until I get report of an NDR from them.
Thanks!

UPDATE 6-30-2014
Finally received an NDR from sending users:

4.4.0 - Other network problem "(336130315, 'error:1408F10B:SSL routines:SSL3_GET_RECORD:wrong version number')"

After some initial research, my first thoughts are an obvious fix; upgrade the server, its old! But I am wondering if there's anyway for me to work around this? Just for the time being.

From what I am gathering so far, Exchange 2003 or rather Windows 2003 doesn't support greater than TLSv1. And also, it has SSLv2 enabled. From the Googling on that NDR message, I see posts about Postfix servers needing to disable 3DES to workaround, or they have SSLv2 disallowed, which my server is announcing as available. My server does not have any of the standard 2003 server protocols disabled though, so it should try SSLv3 right?

Except, I am also reading posts about buggy 2003 server ciphers and broken TLS, so not sure what I can do. Couldn't I just disable SSL/TLS inbound on SMTP?

I'll keep Googling, but not sure how to fix this except to move away from 2003 server.

UPDATE AGAIN

I bet this has to do with Heartbleed OpenSSL upgrades on the sending servers. It looks like Exchange 2003 has can only handle a cipher list length of 64 items (Not verified yet). The ciphers used on Exchange 03 are too low down the list by the sending SMTP, and Exchange fails. I don't know if I'll be able to verify this is indeed the issue, but sure seems likely.

Found this to be interesting:
http://comments.gmane.org/gmane.mail.mimedefang/17927