Are the clients using a VPN or coming in via dialup / PPPoE DSL?
Sounds like an firewall issue with icmp not being able to get though to the server to me really.
Many people block all icmp but "icmp-unreachables" are good and should not be blocked. There are several icmp subsets besides icmp-echo and icmp-echo-reply ( what the "PING" program uses )
such as "icmp-unreachable" that need to be opened up on the firewall(s).
http://www.iana.org/assignments/icmp-parameters
Path MTU Discovery (pmtud) needs "icmp-unreachable" open to the server.
ICMP from the client is trying to tell the server to fragment the packets but the server never receives them so keeps sending normal size packets.
So, you can either allow icmp-unreachables or change the mtu setting on the client(s).
With cheaper firewalls it's pretty much all or nothing sometimes so, lowering the mtu on the clients might be the only way if so.
As a test, try lowering the mtu on a single client
( One of them that hasn't been working ) to something like 1432 and see if that helps, then post back.
Scotty