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?