How about a small script to initially set new player's /home data to a random location on the map? I think this would avoid the ground-zero effect that happens around fixed starting areas, and also eliminate the need to go on a half hour trek to find a clean place to build.
