How can the route between two private IPs go via public IPs?

Solution 1:

There are servers at both ends which are doing Network Address Translation (NAT). As the address passes though these servers the header address on the data packet gets rewritten to that servers Internet address. The server keeps track of which connections belong to which internal host.

Traceroute displays data from inside an ICMP packet indicating whether or not the host was reached in a given number of hops. The NAT routers do not alter this data. As a result you see the address that each host received the packet on.

Normally the servername on the far end in this case has been routed using DNAT (Destination NAT) to a host on the private network.

It is likely that the address is being passed over a VPN tunnel between two sites. The VPN be encapsulating the source and final addresses inside the packets being sent between hops 3 and 7. The effect is the same, although the mechanism is different. The routers at hops 3 and 7 would know the addresses ranges supported by the remote routers, and route the packets accordingly. Leaving hop 7 the IP destination would be 67.0.0.7 with a public address belonging to hop 3. This is invisible due to the way route tracing works. Depending on the VPN protocol some hops after hop 7 may not be traceable.

In some cases you may see an ISP routing over private addresses to a public address. This will appear as one ore more private addresses between two public addresses. If the intermediate routers with public addresses belong to the same organization, it is possible they have routing rules allowing end to end communication without translation.