Hello
You could try telneting to your SMTP server on port 25 and transferring an email using the command line.
The email program you use does this but hides it from you so you dont see what goes on in the backround except when you get those errors or failed messages.
The commands you would use to talk to the other domain should be in the sniffer trace you took,
You could issue those commands , see which one fails and then it should hopefully show you where the problem is.
A sample of a transaction should look like this
telnet `smtp.com 25
smtpserver ready
HELO remotedomain.com
hello pleased to meet you
MAIL FROM: me@here.com
ok
RCPT TO: You@there.com
recipients ok enter
etc.
most should respond to this.
Give it a try see what happens
Cheers