Pré-aviso: tenho um dispositivo de amostra com o aplicativo em questão em execução.
Ok, depois de horas de luta, em um desespero, comecei a mudar as configurações do aplicativo para apontá-lo para vários outros servidores que eu tenho acesso - e finalmente consegui um, onde a conexão funcionou - então eu copiou as configurações de protocolo e criptografia daquele servidor para o item em questão, alterou as configurações no aplicativo para apontar para o servidor original - e funcionou.Para referência, veja as configurações:
SSLProtocol all -SSLv2 -SSLv3
SSLCipherSuite EECDH+AESGCM:EDH+AESGCM:AES256+EECDH:AES256+EDH:ECDHE-RSA-AES256-GCM-SHA384:ECDHE-RSA-AES128-GCM-SHA256:!DHE-RSA-AES256-GCM-SHA384:!DHE-RSA-AES128-GCM-SHA256:ECDHE-RSA-AES256-SHA384:ECDHE-RSA-AES128-SHA256:ECDHE-RSA-AES256-SHA:ECDHE-RSA-AES128-SHA:!DHE-RSA-AES256-SHA256:!DHE-RSA-AES128-SHA256:!DHE-RSA-AES256-SHA:!DHE-RSA-AES128-SHA:ECDHE-RSA-DES-CBC3-SHA:EDH-RSA-DES-CBC3-SHA:AES256-GCM-SHA384:AES128-GCM-SHA256:AES256-SHA256:AES128-SHA256:AES256-SHA:AES128-SHA:DES-CBC3-SHA:HIGH:!aNULL:!eNULL:!EXPORT:!DES:!MD5:!PSK:!RC4:!DHE-RSA-DES-CBC-SHA:!DHE-RSA-CAMELLIA256-SHA:!DHE-RSA-CAMELLIA128-SHA:!DHE-DSS-CBC-SHA:!DHE-RSA-DES-CBC3-SHA
Eu tenho que me contentar com a pontuação do SSL Labs caindo de A + para A- porque eu tive que incluir cifras fracas, mas isso é compreensível. Além disso, por algum motivo, a conexão inicial demora muito tempo (vários segundos) - mas pelo menos os pedidos podem ser enviados:)