[exim] "protocol violation: synchronization error" from our …

I'm having problems sending to a server that appears to be running Exim
4.5x, and uses callout address verification, because our MX - with Exim
4.34 - rejects the callback connection. Actually, I've mentioned this
before, but I hadn't tracked down the exact failure, then. Now, after
manipulating the log options a bit, I've been able to obtain more info,
and it seems like the problem is that our server thinks there is an SMTP
synchronisation error. The following sequence of (slightly rewritten)
log messages should make it clear how the failure occurs:

13:26:21 SMTP connection from [192.168.0.186] (TCP/IP connection count = 2)
13:26:51 1FndOG-004OJa-C1 == example@??? R=lookuphost
T=remote_smtp defer (0): SMTP error from remote mailer after RCPT
TO:<example@???>: host example.com [192.168.0.186]: 451 Could
not complete sender verify callout
13:26:51 SMTP protocol violation: synchronization error (input sent
without waiting for greeting): rejected connection from
H=server6.example.com [192.168.0.186]

So what exactly is wrong here? Is this a problem with our server, or at
the other end? Is there any way I can get around this problem?

- Toralf