So why can't I spent the above output when I have all the ingredients needed for prove? Genuine question, I'm sure I miss something. Also: if I can't spent these kind of outputs it would mean all these tribute transactions are unspendable (assuming thet have been paid using P2PKH transactions, not P2PK).
In theory you can. But your wallet may not be able to. Your wallet software might not be written to recognize transactions sent to those addresses. Your wallet might not be written to watch for transactions that are sent to addresses that it can be spend but did not give out. Your wallet might not be able to produce scriptSigs/scriptWitnesses for those UTXOs. In order to spend such UTXOs, you might need to jump through a lot of hoops and in general do a lot more work even though you have all of the necessary information to create a valid transaction.
A more modern example is mutating a P2PKH into a P2WPKH address. Both P2PKH and P2WPKH encode the hash160 of a public key. If you gave me a P2PKH address, I could use that to create a UTXO that has a scriptPubKey with the P2WPKH script for that key hash in the address. But maybe your wallet doesn't support segwit. Suppose you are using old software or just software that doesn't support segwit at all. The UTXO I created is not spendable by you at this time. Your wallet is not watching for the scriptPubKey in that UTXO, so your wallet doesn't see this transaction. Your wallet does not know how to create a segwit signature and witness even though it has the private key for the public key that is specified by the hash. You have the information, but your wallet is not capable of spending that output.
Scenarios like this are why we shouldn't be doing address mutations at all, whether that be P2PK to P2PKH, P2PKH to P2WPKH, or something else in the future.