This is all pretty weird stuff I must admit
FYI pinging large packets to more-solutions.co.uk worked for me with very consistent results. I tried 1473 and larger with no problem and a quick reply.
It's interesting that you can get the ssh banner page with telnet, I guess it is the fragmented packet thing not working that is stopping a proper ssh connection from being forged, the banner page is probably less than one transmission unit but a full key exchange to get to the login prompt probably isn't.
So it sort of looks like anything that involves data exchange over your MTU size fails, which sort of points to a very broken IP stack somewhere. But given that you have got this on two different machines, with two different connections via two different routers I can't think why. Are there any commons between machines, same kernel ? same firewall configuration ?
I have a larger box of straws somewhere we can try clutching at..bear with me while I try to find it :-)
Ahh here we go, extra large Tesco Value pack....Can you ping from the linux router ? Can you do the ping large packet test from there to isolate everything else ?