Bukkit

1- Set portals, let's say at spawn so players can easily step on/in a portal and be teleported randomly.
Once portals are implemented, you could also create a separate cooldown so players can use them at will.

2- RandomTP limit. On top of a cooldown, players should have a limit of teleports, per day or per log-in session. So players can only teleport a defined amount of times before they are restricted access to the command/sign usage.

3- Admin command /rtp [playername] to teleport said playername. And of course, a permission node for it.

4-WORLD GUARD SUPPORT. Deny spawning in all WG regions or either deny spawn in regions list.