I would spin up more CPUs. Because changing code in the near term is expensive and hard. Spinning up more CPUs is cheap and easy and ensures my company remains successful while I optimize the algorithm.

Using your analogy Bitcoin Core is saying they are going to shut down Bitcoin service to all new users until they implement a new algorithm that hasn't been proven yet and is still years away from being ready.

^ Exactly. The answer should almost always be spin up more cpu's.

Depends on the search algorithm; if it can be parallelized, then modify the algorithm to take advantages of multiple CPUs. If not, then start throwing more threads at it.

In Bitcoin’s case, I don’t think we have a lack of CPUs though.