Before you mark your question 'answered' consider this:
If your bitcon client does not see tx YYY but only sees XXX broadcast-ed then it would seem that only the block your client stored holds the reference to txid YYY (which your client never stored).
In your answer you point to https://bitcoin.org/en/release/v0.12.0#wallet-negative-confirmations-and-conflict-detection as the method that comes to the rescue ... In thier example scenario transaction B 'beats' transaction A in a race to spend the same inputs ...
This method of detection works if your client has seen both network broadcasts of XXX (transaction A) and YYY (transaction B) (because this would be a double spend where YYY beat XXX!)
But seen as your client has never heard of YYY (apart from it's dead-end reference in one block) how will the client be able to use this method when tx YYY was recorded/saved/stored in your PC drive's memory as XXX?
My answer (if you can confirm that tx YYY is un-find-able by your client alone) is;
It looks like some/many miners are changing txids (through malleability)
Testnet3 might be broken/under-un-intentional-attack-from-unsafe-code because malleated txids in blocks point to nothing stored in memory, while the txs that are stored are vaild spends - the txid is not always present in the block.
... like the miner is kind of decapitating some txs
related: testnet3 frequent tx malleability and How did blockr.io see this?