Bukkit

Before respawning, the new randomly chosen location should be loaded in advance.

It's better to show "Please, wait. Area loading" text than spawn the player on void where he might sometimes even drop inside the ground. Not to mention the monsters that may start beating up the player before he has any chances to react.

Alternatively, the player could be spawned inside of a capsule that would protect the player from hostile mobs and ground if spawned inside it.