HOWEVER, just another attack vector to consider (even if it doesn't exist today). Even if you don't see your original Transaction, AND you don't see the TxId/vout spending pair in another transaction on the network, STILL don't just go and directly refund the money to whoever complains that their transaction never showed up.

Maybe an attacker managed to really get your transaction excluded from the blockchain and is holding it back until after your refund. Maybe there is a new attack vector that nobody discovered yet. To be sure, instead re-spend the original Transaction(s) to your own account, wait for a whole bunch of confirmations, and then only re-initiate a new spending out. That way you're using the miners to go and validate on your behalf that everything is still fine with the world.

So in that case if an attacker DID manage to hold back or somehow mutate the transaction, he would now just be holding a double spend that will get rejected.