Debian, Exim4, and remote servers that "greylist"

["John R. Ackermann N8UR" <jra@febo.com>]

I am running Debian Sid with Exim4, sa-exim, spamassassin, and clamav. 
From my end, things are working just wonderfully.

However, I had an email forwarded from an external sysadmin yesterday 
about supposed problems in the way I'm interacting with a remote server 
that does "greylisting."

Here's an extract from that message:

"The mydomain.com MTA running at xx.xx.xx.xx is sending once
and giving up on a TEMP-FAIL.  Given its retry/queue
behavior, sending to a busy server would result in a 'FAIL'.
Strange.

The cause of the TEMP-FAIL is our very light greylisting.
The tuple 
{24.123.66.139,myuser_at_mydomain_dot_com,external_user_at_somewhere_else}
is unknown to (has never been seen by) our servers. [1]  The
flow,
in pseudocode, would be (current config):

	connect: 
{xx.xx.xx.xx.,myuser_at_mydomain_dot_com,external_user_at_somewhere_else}
	if first-sighting then TEMP-FAIL
		start four minute timer
		start counting attempts
	if seenB4 then
		case
			on OK list:
				accept mail
			in trial-period:
				attempt++
				if attempt > 4 then PERM-FAIL (DSN=5xx)
			past trial time:
				if not PERM-FAIL'd
					upgrade tuple to OK
					accept

This behavior has been present for at least six months.

[1] Approved Listings expire after a period.
"

This makes it sound like I'm not responding appropriately to the 
temp-fail message, but I'm not aware that I've changed any Exim4 config 
params that would cause this.  On the other hand, I don't even know what 
params those might be :-)

Is anyone familiar with this problem?  Is there something I should 
change in my configuration to address it, or is the remote system simply 
being silly?

Thanks,

John