Windows tracert sends ICMP requests, while Unix/Linux traceroute sends UDP packets bound for UDP high ports. Use the tracert command from Gaia/Linux and it will work, you must be blocking UDP high ports somewhere in the path but not ICMP echo requests.
Edit: Windows tracert expects to get ICMP echo replies as responses, while Unix traceroute expects to receive Destination/Port unreachable responses. So those latter types of responses could be getting blocked.
Attend my online "Be your Own TAC: Part Deux" CheckMates event
March 27th with sessions for both the EMEA and Americas time zones