So, the problem is fixed.

There was a missing registry entry on both DS:

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\HTTP\Parameters\MaxRequestBytes; Value; 00020000

This value extnds the URL length sent via HTTP(S). Before the URL was incomplete so APNS rejected its payload.