Concept (spoilers in first and third links)
I'm interested in creating something along the lines of the Dahaka from the Prince of Persia: Warrior Within game. In summary, it's invincible throughout the first major section of the game and every time it comes up the main character's only option is to run. Eventually it can be challenged to a fight -- made only all the more satisfying because of it's former invulnerability, in my opinion.
I want to pull this off via a teleport trick. Think this question only with a "yes" answer instead. In this way, the creature would be impossible to hit without some sort of forbiddance, dimensional anchor or other effect, and it's demise ideally wouldn't occur until that segment of plot when the party/character has found an item able to kill it (magical forbidding weapon, artifact, etc.)
If the creature can use a short-range (30' or so) teleportation as an immediate action, how can I keep the party from turning to face it before they find a plot-item keyed to it's weakness? Already I'm figuring on keeping the two aforementioned spells away from them. How else do I need to prepare in order to pull this off?
As Brian Ballsun-Stanton noted in his comment, this is a puzzle monster. In tweaking the rule my aim is to keep it's weakness consistent. Thus, if teleportation is how it works, then it won't work in the area of forbiddance/etc. It's not my goal to chase the PCs all over the campaign world: short chase scenes for plot's sake with an end either within or just out of sight (like an area with innate forbiddance effect if teleportation is used). The Dahaka was loathe to enter water so all the Prince needed to do was find and cross a body of water (almost everywhere in that setting, as it was how the Prince replenished health).
My goal with this question is to either find how to rework the invulnerability to compensate for loopholes (effects dispelling it, etc.) as is illustrated in Tynam's answer but also to support this ability with rules as in HeyICanChan's. Too much more fiat will make it difficult to keep the ability working in a predictable fashion -- very important to this creature's purpose/setup. Encouraging the party to flee is covered over here as KRyan mentioned.