How to reach Velketor's Labyrinth
Velketor's Labyrinth is found in the southwestern section of The Great Divide; depending on your current expansion determines the route you'll want to take. If PoP is out on your server you'll be able to take The Great Divide book in Plane of Knowledge.
Without PoP you'll need to get a Wizard or Druid to port you to Great Divide. If none of this is working out for you - the long route running here starts with taking the boat from North Ro to Iceclad Ocean, crossing Eastern Wastes then entering Great Divide.