Special thanks to Scott Oseychik who worked this out. Check the source.
Issue:
Using Microsoft Office Communicator 2007 R2 in conjunction with Office Communications Server 2007 R2 would intermittently fail to communicate with AOL AIM clients via PIC. Note that this would only reproduce if your OCS 2007 R2 Edge role is running Windows Server 2008 (x64); not Windows Server 2003 (x64).
Resolution:
Essentially, it boils down to tweaking the Windows Server 2008 Edge role to initially establish the SSL dialog using the TLS_RSA_WITH_RC4_128_MD5 cipher suite.
In order to change the cipher suite order, do the following on your Windows Server 2008 (x64) Edge server:
1. Start -> Run -> gpedit.msc -> OK
2. Within the Group Policy Object Editor, expand Computer Configuration, Administrative Templates, Network
3. Under Network, select SSL Configuration, and then double-click on SSL Cipher Suite Order (by default, the SSL Cipher Suite Order is set to "Not Configured")
4. Select the “Enabled” radio button, and in the in the SSL Cipher Suites text box, copy the entire string into Notepad. It should look like the following:
TLS_RSA_WITH_AES_128_CBC_SHA,TLS_RSA_WITH_AES_256_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
5. The objective here is to move TLS_RSA_WITH_RC4_128_MD5 to be a the front of the list. So, in your Notepad document, find TLS_RSA_WITH_RC4_128_MD5, cut it, navigate to the beginning of your notepad document, and paste TLS_RSA_WITH_RC4_128_MD5. The new order should look like the following:
TLS_RSA_WITH_RC4_128_MD5,TLS_RSA_WITH_AES_128_CBC_SHA,TLS_RSA_WITH_AES_256_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,SSL_CK_RC4_128_WITH_MD5,SSL_CK_DES_192_EDE3_CBC_WITH_MD5,TLS_RSA_WITH_NULL_MD5,TLS_RSA_WITH_NULL_SHA
6. Click OK, then restart your Windows Server 2008 (x64) Edge server for these changes to take effect.
We have verified (and re-verified) these steps work, and can now successfully communicate with AOL AIM clients using Office Communicator 2007 R2 via PIC.