The two programs ought to be formally equivalent, in the ideal Prolog model. Usually when you swap two lines in a programming language, the change in semantics is transparent: you've changed the order of operations. But here the change in semantics is implicit. You have to know details about the search algorithm being run under the hood and where those details diverge from the ideal Prolog model. In other words, it's a leaky abstraction over a complex and unreliable machine.

I would call it a leaky abstraction over a simple and reliable machine.

The ideal Prolog model is basically (timeless) predicate logic, eh? I think of Prolog as a useful but not foolproof mechanical calculator for predicate logic, and I'm happy that it works as well as it does with such a simple implementation (chronological backtracking with unification.)

The glass is half-full, rejoice! :-)

Yup, but there's a keg party round the corner, come on!!

I'm too busy building a robotic factory that makes breweries.

"ought to be" under what assumption? Prolog is known not to be purely declarative. If you wish for such behavior use Datalog. If you use a purely declarative language you will run into restrictions that you won't face with Prolog. it's a trade off really.