>It's still in a class of pure "guessing" because just because something looks "correct" early on is meaningless two steps into the future.

It's true that a "good" decision now might turn out to be "bad" later, but whether it's effective in improving a solution depends on the fraction of times that happens, which is almost certainly not 50%. Hill-climbing methods like this are used everywhere in optimisation when you want a decent solution quickly and don't require optimality.

>somewhat analogous to predicting that a coin flip will land on 'heads' if it landed on heads at the last flip

I'm no statistician either, but this is not analogous at all.