[exim] Weird client TLS problem

Hi all,

We have two client machines behind the same router, sharing the same public
IP address. Using Telnet, we can both connect to our remote Exim server.

However, one can't start a TLS session for an unknown reason. 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! It 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