Cannot pay invoice from OBW in CLN due to random pubkeys (private channel)

[shadowcpy]

I am unable to pay an Invoice (generated in OBW) with a CLN node over a private channel as CLN has introduced an abort-early mechanism (ElementsProject/lightning#4404) which refuses to even attempt the payment.
As IMMORTAN uses random public keys for invoices, CLN cannot find the pubkey in the public channel graph and aborts the payment attempt with message: Destination <pubkey> is not reachable directly and all routehints were unusable.
This is the reason I opened #4, which is not the issue though.
(CLN issue is ElementsProject/lightning#5586)

[fiatjaf]

That cannot be the reason, otherwise CLN wouldn't be able to pay to Breez, Phoenix, Blixt, CashApp or Muun, since these all use private channels.

[shadowcpy]

Do all of these also use random nodeIds?
How exactly does payment routing work, if the nodeId is randomized?

Paying to BlueWallet first, and then over the private channel to OBW works perfectly fine, it only fails when the route is constructed by CLN