Yes, I've dealt with these people. If they turn off all ICMP, they often drop fragments as well, making the problem even worse. You can sometimes get them to listen by asking them if their Internet access seems a little "weird" in that some sites work sometimes or downloads are slow or they can't get some email :-)
What do you do when the receiving server is at Microsoft? (mx4.hotmail.com)
Oct 28 11:18:25 exmx2 sendmail[19190]: m9SGHXL4019186: to=some.user@hotmail.com, delay=00:00:52, xdelay=00:00:52, mailer=esmtp, pri=43523, relay=mx4.hotmail.com. [65.54.244.232], dsn=4.0.0, stat=Deferred: Connection reset by mx4.hotmail.com.
I'm not surprised that Microsoft would make such a boneheaded decision as to block all ICMP traffic to their hotmail servers, however would this not cause a ton of customer email to simply be lost? Do they just not care? I guess at this point my only choice may be to lower my MTU size.