An alternate (although mathematically similar) approach would be:
Select a unit of time: let's say five seconds. Call that the Trade Time Slice. Within each Trade Time Slice, all trades are settled equally. If you happen to arrive a nanosecond sooner than the next guy, but you're both within the same 5-s interval (Trade Time Slice), both trades get the same timestamp and price, rather than the strictly FIFO behavior we have now.
Yes, there'd still be an incentive to show up sooner than the next guy, because that makes it slightly more likely that you'll end up in one Trade Time Slice, while the other guy just misses it and ends up in the next Trade Time Slice. But quibbling over 3.2 ns makes that a less than a one-in-a-billion proposition for a 5-second Trade Time Slice. That may still matter to some, and they can try to game it if they'd like, but it'd make High Speed Trading a tiny niche of the market, rather than a major player.
Some purists might say "but that'll add needless friction to the market; they'll be less efficient at finding the optimal price!" To which I would say: prove to me that ordinary investors are harmed by markets marching in 5-s intervals rather than nanoseconds. It may harm high-speed traders, because they won't be able to play their games and siphon their profits from all other traders, but that's hardly the same as saying the market is no longer functioning "correctly".