Not receiving emails from VA.gov - TLS & AES ciphers? 1

Hi,
I'm running Exchange Server 2003 on Windows 2003 R2 Enterprise with all patches with a current Thawte SSL certificate installed on my Default SMTP Virtual Server. We've been unable to receive emails from VA.gov addresses for the past 2 months. VA.gov users receive an NDR:

5.0.0 smtp; 5.4.7 - Delivery expired (message too old) [Outbound_Profile] "(336130315, 'error:1408F10B:SSL routines:SSL3_GET_RECORD:wrong version number')" (delivery attempts: 52)

Based on my SMTP logs, I've found that they send email out using TLS, and using SSLScan, I found that they support the following ciphers:

Supported Server Cipher(s):
Accepted TLSv1 256 bits AES256-SHA
Accepted TLSv1 128 bits AES128-SHA
Accepted TLSv1 168 bits DES-CBC3-SHA

Prefered Server Cipher(s):
TLSv1 256 bits AES256-SHA

Our server supports these ciphers:
Supported Server Cipher(s):
Accepted TLSv1 168 bits DES-CBC3-SHA
Accepted TLSv1 128 bits RC4-SHA
Accepted TLSv1 128 bits RC4-MD5

Prefered Server Cipher(s):
TLSv1 128 bits RC4-MD5

Although we both support 3DES, I also installed hotfix kb948963 that adds AES128-SHA and AES256-SHA, and then rebooted the server. After doing so, my supported ciphers change to:

Supported Server Cipher(s):
Accepted TLSv1 256 bits AES256-SHA
Accepted TLSv1 128 bits AES128-SHA
Accepted TLSv1 168 bits DES-CBC3-SHA
Accepted TLSv1 128 bits RC4-SHA
Accepted TLSv1 128 bits RC4-MD5

Prefered Server Cipher(s):
TLSv1 128 bits AES128-SHA

However, I still can't receive email from them, and I also stop receiving emails from other mail servers. I ran a Basic Receiver Test on checktls.com and found that it failed with error:
checktls cannot proof e-mail address (reason: mail from rejected)
The cipher used was AES128-SHA

After disabling AES128 and AES256 via the registry, I re-ran the Basic Receiver Test, and then all tests passed. The cipher used was RC4-MD5.

I'm stumped, and would appreciate any new ideas.
Thank you.