Quake 3 has also got pretty sophisticated client side prediction code to make things seem instantaneous to the players. This is much more complicated to do in Minecraft where the whole terrain may change and lots of race conditions may arise.
Network game code may seem like a solved problem but it's still a complex distributed soft real time software system where solutions are highly application specific. What works for Quake isn't necessarily good for Command and Conquer or Minecraft.
But I agree, there is no reason for Minecraft performance to be so bad when there are only 2 people on a server just mining one brick at a time!
Not quite. The map in Minecraft changes. But if you optimize the game for the "constantly changing" case, when it usually changes less than 1 block per user per 10 seconds (and even that is high), then you're going to end up with code that doesn't handle normal behavior very well.
Quake III was doing server-side calculated game state 16 years ago stupid fast for 32 players moving quickly on dial-up modems; I doubt it'd be much of a problem to do these days with even a lousy architecture for a game with much much slower movement, e.g. Minecraft.
This problem has been solved pretty well many many times before.