There is an important distinction that needs to be made here. Traffic that flows out of a DSL connection changes form a few times along the way. When it leaves your computer, travels through your network and hits the modem, it is Ethernet traffic. Most consumer grade equipment defaults to 1500 and the modem your ISP sends you is also probably defaulted at 1500. If you were to change the MTU, ALL interfaces between your PC NIC and the modem (including the modem) would need to be changed.
Once it leaves the modem, it is officially on the ISP network and is running as ATM traffic. This interface, and the rest of the path, you will have no control over. ATM traffic runs at a different MTU typically, but it depends on the equipment and the network. For example, cisco ATM equipment runs at 4470. An ISP network's ATM cloud may consist of Juniper, Cisco, Alcatel, Nortel, Fujitsu, Adtran or any of many other vendors. It may also interface with other provider's networks and their equipment. In other words, you have no way of knowing what will happen to packets once they leave the prem - and your ISP may not even have an idea of the entire journey of a packet either.
Once it reaches the other side and becomes Ethernet again, the MTU on the other network will then be a factor. If you don't know anything about the network you're sending to, it is best to assume it is 1500.
Also, ATMs most likely will not be set to block fragmented packets. All that will happen if a packet too large for the interface's MTU comes through is that the packet will be broken down in to smaller chunks and passed on. This may not be the case with the network at the other end.
If you send packets that are equal to or lower than the Maximum MTU on the chain, they'll get through without a problem. If you send higher, there is a chance they'll fragment or even be discarded.
What it comes down to is that you really should be aware of the MTU across the entire path if you are going to use anything higher than 1500, otherwise it is safest to just default to 1500.
MTU is a link-local issue in terms of 'works' vs. 'doesn't work'. If the machines on both ends are configured to use an MTU appropriate to their specific link, then the routers in the middle should fragment packets as appropriate to get data through. Performance will suffer, but you should get traffic, even if ICMPs are being blocked in the middle.
Of course this won't happen if the routers between have one or more links with a misconfigured MTU, but someone would probably have noticed that before now.
As far as checking where / if ICMP is blocked, I suggest traceroute. If you're using Linux, the most recent version in Ubuntu comes with a moderately detailed description of ICMP blocking related issues, and it should give you a good clue as to where the block is coming from. Since you have access on both sides, you should be able to verify in each direction.
Best Answer
PPPoE requires 8 bytes of encapsulation/header data, which is why you can only operate with a 1492-byte MTU on Ethernet. But normally, this sort of thing is sorted out by path MTU negotiation.
If someone's blocking ICMP, then path MTU negotiation will not work.
Your options are get rid of PPPoE or change the MTU on the remote system to deal with your semi-broken connection. And yes, I realize that both are not ideal.