Before I found Opticraft, I was giving another server a try. (Ended up giving up stuff away and quitting.)
That server, however, had a nice plugin that might work for this situation, and could otherwise improve this server.
When you typed "/warp wild" it would take you to a different place, every time.
This allowed users to be more spread out, allowed you to actually have some land, etc. (Sometimes it spawned you in the ocean, but that's a small price to pay. And I don't know what all you can do when making a plugin, but it might even be possible to regenerate coordinates if it finds you're in an ocean biome.)
This same technique could be implemented in the Nether, though you would have to be 100% sure you took precautions. (Spawning people into lava and such.)
Heck, I'm not against the idea of implementing it for the normal world too.
Just an idea that could help the situation that over-populated worlds bring.
-Dave
Edit:
This also reminds me of the first server I ever played on.
Whilst waiting for some plugins to support the new version of bukkit (or maybe it was bukkit to support the new version), due to a majority vote, the main admin cleared the wild.
This however, meant that he had to transfer over everything that was to stay individually.
Needless to say, stuff got left, warps were screwy, etc.
This is truly a situation that needs to be handled from the start, to make sure it never happens. (An example being a plugin I saw that automatically planted a new tree when when was chopped down.)
And ugh, this voting popup is getting annoying.