As I pointed out on the mailing list observing the chain for matched orders tells you nothing about whether or not those orders were ever published; that is, whether or not they're entirely fake and don't represent actual market depth.
As I said in the text you quoted, a filtered average over previous block solves this. Unless you are assuming the attacker has majority hashrate, in which case you're screwed anyway.
It's the same logic that came up in the discussion about announce/commit sacrifices. As for "other systems", remember that I did recently publish Tree Chains specifically to act as a general purpose proof-of-publication system for all uses with highly adjustable security/scalability tradeoffs.
Yes, and that would be a decent basis for a proof of publication system for orders. You could even shard based on market pairing so that people only have to validate what they're interested in. But validation of of the trades themselves should be separate, to achieve better scaling properties.