I believe that Taiwan (TSEC) does this, although I can't find a reference for it now.

I heard of that, too, but couldn't find a reference the last time I checked, either.

This is actually how most of the European equities markets start and end the trading day. During the auction period, anyone can submit an order at a given size at price. When the auction ends, the exchange matches at the price that maximizes the number of shares traded. The rest of the trading day operates in what is referred to as a "continuous auction" where orders are matched continuously based on price/time priority.

What happens if there are more buy orders than sell at the same level (or vice versa)? Who gets priority on that fill?

To be clear, the way (most) exchanges solve this problem now is by what's called "queue" priority. The longer an order has been resting at a level the higher it's priority is.

This means that those who can respond faster can get into a price level sooner. Breaking this out to minute bounds doesn't mitigate their advantage in any way shape or form.

It is hard to know what the results of a change like this would be. I suspect it would make the markets much less stable as there would be less information to make accurate prices, causing huge variances on minute long ticks.

This is not a problem that today's electronic markets avoid. They have to answer your question too!

Either first-come-first-serve, but that would give you some form of high-frequency again, or you just pro-rate them or fulfil them randomly.