It could be that the transaction was broadcast too late to be included by the producer. There is a race condition where if you broadcast it, but the producer doesn't receive it in time and so it is "stale" and not included in the blockchain.
Thanks for the explanation. Does "in time" mean that a POW based on the hash of block n is only accepted if it is included in block n+1?
That would severely (and unnecessarily IMO) punish miners on a "high"-latency connection. For example, with a (perfectly normal) latency of 300ms a miner can effectively only mine from t+0.3s until t+2.7s, which is a 20% reduction of efficiency!
Moreover, this means that the currently active witnesses automatically have a higher than average chance to have their own POWs included in the chain in time.
Even worse, it means that the currently active witnesses can deliberately drop POWs from other miners, thereby increasing their own effective hashrate!
IMO there's no reason to not accept POWs that are based on the hash of one of the latest 21 blocks (for example).