Why is AD login slow over VPN?

We have installed a number of domain member computers running server 2012 R2 into remote offices in  third party locations. The majority of these installations have been fine without any issues, but with one particular network provider we are having issues with extremely slow login with AD user accounts. At present member systems take over two minutes to complete login to the system with RDP.

The remote offices in question are connecter to our network using a VPN tunnel. I have completed the following tests to try and diagnose the issues.

[1] Confirmed that firewall rules and either end of our network do not have any restrictive rules.
[2] Confirmed that the third part firewall rules are not blocking any traffic between the domain controllers and the remote office.
[3] Confirmed that no NAT is in place between the remote office and head office.
[4] Used PortQry to run tests in either direction between DC and Client.
[5] The third party has lowered the encryption level on the VPN tunnel.
[6] The third party has configured the maximum segment size on the router LAN interface to 1360.
[7] Configured the AD member computer to use TCP for Kerberos.

So far nothing we have tried has had any effect on the speed of login using AD accounts.

Regards,

SWilson