At the limit of complete generality the Halting Problem guarantees your statement is correct. But it also appears to be extremely difficult to do this at runtime without side-effects that change global state such that information leaks. The real cost for speculative execution may be that it can't be done in a purely-functional manner.
So what?
Most workloads / customers are much more about performance than security. We can trivially remove such attacks by switching off all speculation (branch prediction, caches, OOO, prefetching). Indeed you can buy CPUs like that, and they are used in environments where safety is of extreme importance. The cost of this is an orders-of-magnitude loss of performance Most workloads (e.g. Netflix streaming, Snapchat filters, online advertising, protein folding, computer games, Instagram, chat apps) are simply not security sensitive enough to care.
Building a competitive general purposes CPU costs a lot (probably > $1Billion end-to-end), and who would buy a CPU that is safe against Spectre but 3 orders of magnitude slower than the competition? (Not to mention that there are many more dangerous vulnerabulities, from Rowhammer to Intel' Management Engine, to rubber hose ...)
One of the things about Itanium that I do know is that it's basically VLIW. And VLIW is a technology that sounds really good on paper, but it turns out that you just can't get that good results for realistic workloads--they've basically been abandoned everywhere they've been tried except for DSPs, where they live on apparently because DSPs have so few kernels they care about.
And speaking as a compiler writer, no compiler will ever do a good a job as the hardware can at maximizing instruction-level parallelism. The compiler is forced to make a static choice while hardware can choose based on dynamic effects that the compiler will never be able to predict.