They fucked up by assuming that if the txid they sent didn't make it into a block, then no other txid could have spent those coins so they didn't bother checking the blockchain to make sure that was the case.
Wasn't that a reasonable conclusion from sendtoaddress being updated to return a txid?