RFC 1918 address on open internet?

It is permissible for routers to connect to each other using RFC1918 or other private addresses, and in fact this is very common for things like point-to-point links, and any routing that takes place inside an AS.

Only the border gateways on a network actually need publicly routeable IP addresses for routing to work. If a router's interface doesn't connect to any other ASes (or any other service providers, more simply), there is no need to advertise the route on the internet, and only equipment belonging to the same entity will need to directly connect to the interface.

That the packets return to you this way in traceroute is a slight violation of RFC1918, but it isn't actually necessary to use NAT for these devices as they don't connect to arbitrary things on the internet themselves; they just pass along traffic.

That the traffic takes the (possibly circuitous) route through several organizations that it does is merely a consequence of the operation of exterior gateway routing protocols. It seems perfectly reasonable that Microsoft has some backbone and some people have peered with it; you don't have to be a wholesale ISP to route traffic.

That the traffic has gone through multiple series of routers with private IPs, transiting through ones with public IPs in between, is not especially strange - it simply indicates (in this case) two different networks along the path have routed the traffic through their own routers which they have chosen to number in this way.

Not just RFC 1918...also RFC 6598, i.e. 100.64.0.0/10 CGN space. Both of those are private networks, but the latter is more recently standardized and less known.

This isn't unusual from a traceroute standpoint. You aren't actually talking to those 10space and 100space hosts directly, you're sending packets with incrementally larger TTLs to your next hop router. To keep the answer from getting overly long, this Wikipedia link summarizes the process.

What is unusual is that that this packet traverses public IP space, and is then tunneled through private IP space to reach a "public" net yet again. 157.56.176.94 is owned by Microsoft, and the packet traverses MS owned networks before hitting the private net...so it's simply what Microsoft is choosing to do with their network space at both ends of the private space. They advertise the routes; the other routers just do what they're told.

As a general rule, no, network operators generally do not expose their private nets along a route to public IP space from outside of their network. That's why this is so unusual.

(it could be a missing route somewhere on their border, causing the packets to traverse a non-optimal path that eventually reaches its destination, but I'm not a networking guy and someone can probably take a better stab at it)