I have found 4 ways to get around the problem:
1) A somewhat effective fix is to have your users use a cache/proxy server.
2) Have your users lock there MTU to 1492 not 1500.
3) Some CPE routers will force 1492 MTU sessions.
4) Try to explain that ICMP is not just pings rate limit it don't drop it.
Cisco's writeup on the problem: