In answer to your query ...

I think it is unlikely that the TTL exceeded reply has been
completely filtered, though it's possible.  Another
possibility is that perhaps all outgoing packets are being
rewritten to have a higher TTL?

I suppose this would result in the start of all traceroutes
slowly timing out... but higher TTL values (the 10th, 15th
or 20th hop...) still being functional.

If you like, try my (somewhat buggy, but functional!)
traceroute implementation or another one that supports
skipping the first few hops - ie: starting the traceroute
from 6 hops away (TTL 6).

( - Perl based )

Otherwise, for the first few (8 or so?) hops you can set an
option in the header of a standard ICMP ping to 'record
route'.  This is the -R option in standard unix traceroute.

me@laptop:~$ ping -R
PING ( 56(124) bytes of data.
64 bytes from icmp_seq=1 ttl=253 time=491 ms

64 bytes from icmp_seq=2 ttl=253 time=493 ms
NOP     (same route)

--- ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 1007ms
rtt min/avg/max/mdev = 491.761/492.690/493.620/1.164 ms

- Walter