It is not possible that an oracle could be truly random and decentralized at the same time.

And the concerns raised in the comments seem to be right. If solving mathematical problems is profitable here, is PoUW not merged mining to some extent? Allowing consequently "zero cost attacks", or something very similar to zero cost attacks?

The Bitcoin protocol is not very well suited to the needs of merged mining. Much more than just the algo would have to be changed, and even then the current level of security is unlikely to be maintained.

Merged mining (the real one at least) can be and is a great solution, but for other coins with a different purpose than Bitcoin.