Here comes my theory for how this breaks my scenario:
When the INVITE then reaches the first hop (first Path header, also Kamailio), relay() sees that the Route header is itself and/or sees that there is only one Route header.
The observed result is that the first hop then sends the INVITE directly to the Contact, instead of via the second hop.
Is there a particular reason the combined path is not split on lookup? Is this a bug / oversight? Am I crazy?