It turned out that the limitation of maximum supported Diffie-Hellman key size on .NET CF was actually not a bug. Apparently, there was a 2048-bit limtation on Windows CE 5.x, which is what Windows Embedded Handheld 6.5.3 is based on as well (despite its name). Windows CE 5.x, "Microsoft Enhanced DSS and Diffie-Hellman Cryptographic Provider" is actually available, but it is apparently limited to Diffie-Hellman key sizes of 2048-bits and lower. Later versions of the OS, such as Windows Embedded Compact 2013 (based on Windows CE 8.0 kernel), do support 4096-bit keys (which we have been limiting to 2048-bits unnecessarilly).
Unfortunately, this means that there is no perfect solution for this issue, although there are some possible workarounds:
a) If the server supports Elliptic-Curve Diffie-Hellman, use that instead of classic Diffie-Hellman. To take advantage of it, use [Rebex.Castle.dll eliptic curve plugin](
https://www.rebex.net/kb/elliptic-curve-plugins/) (based on open source BouncyCastle project and suitable for all .NET CF 3.x platforms) at the client.
b) We could enable usage of 4096-bit keys in our managed Diffie-Hellman implementation. This might work, but unless your devices are unusually powerful, these calculations might take a very long time.