You should put together adventures that REQUIRE teleporting. Make them use those teleports for important tactical and story reasons... why has no one else plundered this temple?! Because it requires the Teleporting Weenies from Hell to succeed!
PS
This. As for challenging them, just remember to count grabby monsters and melee-heavy monsters as lower level than they actually are.