> I'm fairly certain that changing the MTU should be the LAST thing that a helpdesk or general support staff should be doing, and instead additional tests on configurations, etc. on the system itself should come first.

Most definitely. Changing an end system's MTU should definitively be only the last straw. 

If there is a reduced MTU link somewhere in the path (and if PPPoE is in the game chances are high that there is), then make sure...

... on the network, from end system to router/gateway
 - full support for Packets/Frames with a L3 payload size of 1500 on all links.

... on the router/gateway which has the reduced MTU link attached:
 - respects the *don't fragment* bit set in packets travelling through (in extenso: does not do "df-bit ignore")
 - sends *ICMP unreachable,  Fragmentation Needed* messages (Type 3, Code 4) for packets too large to fit into the reduced MTU link.
 - performs TCP MSS clamping (Cisco speak: "ip tcp adjust-mss") to an appropriate value (e.g. 1452 for an 1492 MTU link), if possible in both directions. 
 - (although very exotic) check the given DHCP service for the subnet/VLAN does make use of option 26 (MTU) and pushes this option to the clients

... on the end systems (although the details and how-tos of this will be off-topic to this board):
 - Investigate if some/all end devices ingest and process DHCP option 26 (MTU) or if they ignore it. Only if DHCP option 26 is present at all.
 - Investigate if the given IP stack supports PathMTUDiscovery and if it is enabled (i.e. if the IP stack actually ingests and processes the fragmentation needed messages) 
 - Check if the device's 'security features' (as in "host based firewall") prevent ingestion of *fragmentation needed* messages because some 'security admin' ruled that "ICMP unreachables are bad, m'kay?", resulting in broken PathMDUDiscovery support.


Although this is speculative, the symptoms you describe might be caused by this:
 - Router/Gateway does support PathMTUd, and does send *Fragmentation Needed* Messages (ICMP Type3/Code 4)
 - Router/Gateway does *not* perform TCP MSS clamping.
 - Most end systems ingest and process the MTU suggestion in the ICMP Type3/Code4 messages correctly. They don't have to rely on MSS clamping. 
 - Few systems won't/can't receive or process ICMP Type3/Code4 correctly and would have to rely on TCP MSS clamping. 

The true solution of course would be to have proper PathMTUd support on both Router/GW and end systems.  The second best solution is to implement TCP MSS clamping correctly.