In my experience, problems like this are caused by misconfigured routers much further up the internet than "anyone" is likely to have any control over that don't fragment and unfragment properly and/or don't pass ICMP fragmentation required packets.