Honestly, I'm not a big fan of the whole nightcrawler-esque teleportation. The way I see it, it's a somewhat gimmicky method of increasing difficulty.
My opposition to it hinges on two primary points, one practical; I generally have large forts, which are impossible to fully patrol if I want to have any sort of military presence on the gate, so a teleporter would be able to have a field day in my warren of tunnels, picking off the lone haulers etc. without any reasonable fear of reprisal. While cooldown times and similar would help, I honestly don't think they would remove the underlying problem.
The other issue is conceptual; I stuggle to see how the teleporter would be able to find his desired location without having reports of where the actual tunnels are, and blind teleporting is pointless, as if he missed by even a square, he'd probably be intombed in rock.
Personally, I'd prefer you get something like a shaman who can infilitrate into the base, then set up a portal, whereby a few hundred gobbos pour out (for fps fans, think TF2 with an engineer setting up a forward tele). If he gets to his desired location, he opens the portal and scarpers, after which the horde flows out, and if detected, he'll try to cast the portal then and there (hence while a peasant discovering him would be bad, a fortress guard finding him results in gobbo paste). Like the aforementioned engineer, this unit isn't intended as a combatant.
For survivability reasons, they would have to have sneaking skill, and it would probably help if they could dish out some fireballs or similar in the case they do get caught. Further, giving them the ability to fly, survive magma or do some other things would be at least concepually explainable (it's a magic user after all), while allowing them to bypass the majority of basic defenses without making up a nigh-invincible magma-breathing-tunneling-troll-worm (of doomyness) that has no conceptual reasoning behind it, let alone an omniscient space bending warrior (of doomyness). You would still have to patrol your fort near the entrance, along walls and around the moats, but you wouldn't be expected to guard a z-15 exploratory tunnel from the X-men.
tl;dr? teleporter = bad, infiltrator with portable stargate= good.