When you post a transaction, the public key is in the transaction (inside the field "sigscript") . With the public key known you only need 2^(66/2) checks (instead of 2^66), which can be done really fast.
So some bot watched the address, obtained the public key, computed the private key from it, and front-ran the original submitter probably with a deal from a mining pool to make sure his transaction is enforced.