...
The UXTO constraint may never be solved in an acceptable (sub)linear way, or the solution(s) could for political reasons never be implemented in BTC.
...
Almost certainly 'never' by any realistic definition of various things.
UTXO is the core of the information of who has what. Coinage in circulation solves the problem in several ways, the most important being loss of information (which is why TPTB would like to and likely will at some point do away with it.) Coinage is segmented into equal units which can scale due to the aformentioned loss of high resolution info. UTXO is a minor optimization in the segmentation, but that optimization vanishes with popularity. Right now it is early and there are plenty of keys which control the equivalent of trillion-dollar bills. That would vanish if the rather absurd dream of universal usage came into existence. It would be relatively easy for Google-scale entities do the bookkeeping on individual satoshis in near real-time and relatively impossible for others to do so.
Solving 'the UTXO problem' would require what is by most definitions 'magic'. Perhaps some future quantum-effect storage, communications, and processing schemes could 'solve' the problem but I'm not expecting to pick up such technology at Fry's by the next holiday season (Moore's law notwithstanding.)