[keepmesmall]

The destination IP could be hidden opportunistically?

Send the destination IP for high-priority requests and retry without the destination. Low-priority/long-latency requests would always hide the destination.

... I can't articulate why, but I feel even this introduces a very large amount of hidden complexity. It solves efficient routing and freedom in part, but does not consider privacy.

[solotronics]

I don't see how you can hide destination IP. Each router has to know the destination IP to determine where to send the packet, yes there are some cases such as MPLS/VXLAN/v4VPN where the packet is encapsulated inside more routing info but for it to get to its destination the routers have to have an IP.

[keepmesmall]

If the routers have public keys it's possible, then the client has to determine (some or all points on) the route. I think future protocols will track use and payment via client-provided keys which are somehow linked to their ISP.