Exchange 2007 Cipher Suite Order
Apparently it is not possible to reorder the SSL Cipher Suite. My Windows Server 2003 Exchange 2007 server will always and forever offer AES-128 before AES-256 unless I disable the use of AES-128 by modifying the following registry key.
HKLM\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHANNEL\Ciphers\AES 128/128 : DWORD Enabled=0x0
With Windows Server 2008, you can just change the SSL Cipher Suite Order.
I know this is an old post, but maybe it will help someone else. Here is how to change the cipher order for 2008. I had this same problem that took me months to work out between Microsoft and the other side that required AES 256. The other side could not even tell me how to accomplish this. i had to get forwarded around microsoft for weeks 19 times before I got this:
On your Exchange bridgehead: gpedit.msc > Local Computer Policy > Computer Configuration > Administrative templates > Network > SSL Configuration Settings > SSL Cipher Suite Order > Enabled
Cut out what is in the "SSL Ciper Suites" field (paste to notepad for safe keeping) and copy the following into the "SSL Cipher Suites" field (dont worry, it will all fit)
TLS_RSA_WITH_AES_256_CBC_SHA,TLS_RSA_WITH_AES_128_CBC_SHA,TLS_RSA_WITH_RC4_128_SHA,TLS_RSA_WITH_3DES_EDE_CBC_SHA,TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA_P256,TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA_P384,TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA_P521,TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA_P256,TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA_P384,TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA_P521,TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA_P256,TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA_P384,TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA_P521,TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA_P256,TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA_P384,TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA_P521,TLS_DHE_DSS_WITH_AES_128_CBC_SHA,TLS_DHE_DSS_WITH_AES_256_CBC_SHA,TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA,TLS_RSA_WITH_RC4_128_MD5,SSL_CK_RC4_128_WITH_MD5,SSL_CK_DES_192_EDE3_CBC_WITH_MD5,TLS_RSA_WITH_NULL_MD5,TLS_RSA_WITH_NULL_SHA
Might have to restart some services or reboot the server. Hope it works out.