#1 - turn your sendmail logging/debugging setting up as high as it will go for just long enough to capture some of these events. (then turn it back to its previous setting)
#2 - try using script and then telnet to capture an SMTP session (Done by hand) with the MTA at the receiving end. This can be a little tricky and requires a good understanding of how SMTP transactions are done so you can emulate it by hand.
Thank you all for the suggestions, I think we may have pinned down the problem. This list is a great resource, props to all the experienced users who put in time answering questions here. :)