[exim] Weird STARTTLS problem

Hi all,

We have two client machines behind the same router, with the same public
IP address. Using telnet, we can both connect to a remote Exim 4 SMTP
server.

However, one can't start a TLS session for an unknown reason (454). Here
is the trace for the telnet client succeeding:

220 alaska.noelios.com ESMTP Exim 4.63 Thu, 10 Apr 2008 16:05:17 +0200
EHLO colorado
250-alaska.noelios.com Hello m215.net81-67-81.noos.fr [81.67.81.215]
250-SIZE 52428800
250-PIPELINING
250-STARTTLS
250 HELP
STARTTLS
220 TLS go ahead

Now the one for the telnet client failing:

220 alaska.noelios.com ESMTP Exim 4.63 Thu, 10 Apr 2008 16:06:32 +0200
EHLO colorado
250-alaska.noelios.com Hello m215.net81-67-81.noos.fr [81.67.81.215]
250-SIZE 52428800
250-PIPELINING
250-STARTTLS
250 HELP
STARTTLS
454 TLS temporairement indisponible

The last 454 message means "temporarily unavailable" in French. We
couldn't find additional debug/log information on the server.

This problem is driving us nuts! This fails with Thunderbird in a
similar way. Both clients are running Windows XP Pro SP2. The Exim
server is on Debian Etch.

Any idea?

Best regards,
Jerome