Along the lines of horse13's comments I have found a firewall set of rules that allows only the outbound and inbound ICMP I want (two separate rules) and two other rules that deny all other ICMP connections (one for inbound, one for outbound). This way I can run traceroute out but will not respond to an inbound traceroute, or will allow an inbound echo reply but wont send one. This seems to keep things working fairly smoothly even if it did take a little poking around to find the right mix.

I don't know if this will help corndog's e-mail but it works for me.