As I said, we have a test installation of each partner system properly set up in our local network. No tunneling, no firewall, no heavy load neither on our, nor on the partner system.
I'm sure, the network can't be the cause of that discrepancy. I checked that using Wireshark: Network traffic happens AFTER that time consuming call.
When I access the service via soapUI, no problem, therefore I can't blame that problem on our partner.