It's not a static decision though - the memory accesses can still be reordered when %ebx != %esp, though of course this only ends up visible where there are multiple CPUs involved.

For example, consider the case above and assume that the initial conditions are:

  (%esp) == 0
  (%ebx) == 0

Now imagine we have a second CPU executing simultaneously, with the same %ebx and %esp as the first CPU, but executing this:

  mov $1, (%ebx)
  mov (%esp), %eax

Now if there was no reordering, either one or both CPUs must end with %eax == 1. However, the hoisting of loads before earlier stores means that you can actually end up with both CPUs have %eax == 0 after this executes.

You're correct about it being possible for other CPUs to see "crossed" loads/stores, but within one CPU/stream of instructions the programmer-visible ordering is absolutely preserved, because if it wasn't, a lot of existing software would break. In your example, if ebx == esp, and both CPUs executed those two instructions, then they must both see eax == 1. I think you had this scenario in mind instead (where A and B are different memory locations):

CPU 1:

  mov $1, (A)
  mov (B), %eax

CPU 2:

  mov $1, (B)
  mov (A), %eax

Where eax == 0 on both CPUs is definitely possible.

We are of course in violent agreement.

The point to note is that the decision on whether or not the reordering can occur, based on whether or not A and B are the same or not, is made dynamically at the point of execution.