É permitido que os roteadores se conectem uns aos outros usando RFC1918 ou outros endereços privados, e na verdade isso é muito comum para coisas como links ponto-a-ponto e qualquer roteamento que ocorra dentro de um AS.
Somente os gateways de borda em uma rede precisam de endereços IP publicamente roteados para roteamento para o trabalho. Se a interface de um roteador não se conecta a nenhum outro ASes (ou qualquer outro provedor de serviços, de forma mais simples), não há necessidade de anunciar o roteamento na Internet, e somente o equipamento pertencente à mesma entidade precisará se conectar diretamente ao interface.
Que os pacotes retornam para você desta forma no traceroute é uma leve violação do RFC1918, mas na verdade não é necessário usar NAT para esses dispositivos, pois eles não se conectam a coisas arbitrárias na Internet; eles apenas passam o tráfego.
O fato de o tráfego utilizar a rota (possivelmente em circuito) por meio de várias organizações é apenas uma conseqüência da operação de protocolos de roteamento de gateway externos. Parece perfeitamente razoável que a Microsoft tenha algum backbone e algumas pessoas tenham perscrutado isso; você não precisa ser um ISP de atacado para rotear o tráfego.
O tráfego passou por várias séries de roteadores com IPs privados, transitando por meio de IPs públicos intermediários, não é especialmente estranho - simplesmente indica (neste caso) que duas redes diferentes ao longo do caminho rotearam o tráfego por meio de seus próprios roteadores que eles escolheram para numerar dessa maneira.