For what it's worth I once had to deal with an issue where we had all of our circuits on a single Cisco router.
Due to the router connections being over utilized they had to move a couple of our circuits from a Cisco router over to a Juniper router.
As it turned out, over a longer period, it didn't work out.
They wound up having to move all of our circuits back to the same Cisco router and bumping some other folks off.
The problem for us (even though both the providers engineers and us never really understood the problem) seemed to revolve around VPN encapsulation. Once all the circuits were on the same router the problem was mitigated (although we still had to set MTU statically on individual workstations).
The fact of the matter is that providers use encapsulation other then VPN to route traffic (one example would be GRE) which is extremely useful but is still what it is, it adds to the packet size and thus has problems traversing (misconfigured interfaces?).
Actually a simple packet grabber (wireshark) might go a long way to see what is going on, but obviously that would have to be inside the host network, inside the problem to see any malformed packets.
