I've disabled PING access from outside to inside on my PIX 520, but I can't stop traceroutes...
Below is the 3 lines I've used to stop PING access from outside to inside and allow PING & traceroutes from inside to outside:
conduit permit icmp any any echo-reply
conduit permit icmp any any unreachable
conduit permit icmp any any time-exceeded
Trace route can use high random UDP ports too. Are you allowing UDP or using the established command in your config? What version of code are you running? Conduits are also processed in the order you see them in the config so if there is something more general permitting it prior, then maybe thats allowing it. You can use debug icmp trace to see the packets during testing.
I'm not allowing UDP or using the established command. Running IOS 5.1. Don't have any other high random UDP statements listed prior. I thought that the established command was only used for routers not PIX's? You learn something new everyday...