[Man Who Walks At Night]

Actual stats for this monster are your problem. 

Not everything needs stats being "invincible" is sometimes enough

[Exodus]

Not everything needs stats being "invincible" is sometimes enough

Everything "alive" should be killable, banish-able, or otherwise solvable.
Giving the players something to chase them around will get boring when they figure out that it can't be killed. My ghost thingy, called an APOLLONIAN WIGHT on http://www.keiththompsonart.com didn't have stats because I made it up on the fly. However, the moment I made it up I also gave it a simple kill-condition. It would dissipate if attacked or the "host" was healed or cleansed magically. The figurine was similar, it wouldn't actually do anything but loom in the background and move ever closer if looked away from. Since there was only one there was never a threat of the party being cornered unlike the Who episode "Blink". It was destroyable as any figurine would be.

Now the party didn't know that of course since on top of them not knowing the Shadowrun 'verses every detail, the figurine was also a custom doodad.

[Dead Monky]

Everything "alive" should be killable, banish-able, or otherwise solvable.

Obviously not a Lovecraft fan. 

[CanRay]

"If it bleeds, we can kill it."

"Um, spirits don't bleed."

"...  OK then.  New plan."

[Man Who Walks At Night]

Everything "alive" should be killable, banish-able, or otherwise solvable.

That is not the same as needing stats though, and it might very well be invincible in the given situation - but vulnerable at a later time. Just because they runners cannot kill it NOW doesn't mean it cannot be killed later, sometimes they runners just NEED to run into something not covered by rules, something they just simply need to avoid - keeps them on their toes, as long as its not the standard opposition, but happens once in awhile I find it perfectly fine

[CanRay]

My Deadlands ground had, I think, five definitions for "Dead".

"Absolutely Dead" involved confirming the body and using acid, IIRC.  Even then, they worried, however.  But that's Deadlands.

Shadowrun, never consider the opponent dead until their body has been cut up and fed to the Ghouls.  And even then, expect family to be really slotted off.

[Dead Monky]

Try Call of Cthulhu.  The only characters you can ever be sure are really dead are your own.  And even then it can be a little iffy.

[Exodus]

That is not the same as needing stats though, and it might very well be invincible in the given situation - but vulnerable at a later time.

I, personally, don't like including anything that's both a threat and invincible at any particular time in my campaigns. If they're done very well they can be fun in a 'journey is more important than the resolution' type way but the unstoppable is boring IMO. I've been in too many games where we've fought something that was "scripted" to be unbeatable. Go ahead and hit players with things they should run away from, lord knows I have, just don't do it with a single unstoppable enemy. A more believable strike team or a taskforce built to stop those particular runners. Make sure to express to them that a Bolivian Army Ending isn't what you're going for, lest they fight to the death in an alley with a perfectly accessible sewer escape behind them.

Your mileage may vary of course. I've talked with players who's favorite moment in a DnD 3.5 campaign was fighting to the death over a cart or bricks.

Edit cause of posts:
Letting the player think they've killed someone/thing for a time is fine if there's some reason (ingame or rationalized) for the entity to survive.
http://tvtropes.org/pmwiki/pmwiki.php/Main/NoOneCouldSurviveThat
However, don't abuse it, the second or third time a BBEG survives certain doom your players will either A. Prepare for his eventual return or B. Shoot the body into the event horizon of a black hole as I demanded we do to a Sith Lord a Star Wars game, but he came back as a Sith Ghost and found a cloned body of course.....

[savaze]

Even if something is 'killable' doesn't mean that the players are gonna be the ones to do it...

The closest I can relate to you came from an old AD&D where the players were trophy monster hunters.  Yeah they were nuts.  Their mage had heard of this crazy creature called a Tarrasque through his research through the years, so they decided it was time to take it on.  Well if you've ever seen the stats, pre 3e, it wasn't something to trifle with.  They spent ~30 hours pursuing and learning how bad of a mamajama the thing is, and how dumb it would be to continue, and they still pursed (late night college gaming is me trying to rationalize it - maybe they were rp'ing low WIS scores).  The players were considered fairly high level (14+) and there was ten of them that campaign.  In the end I kept one player 'alive' just so that they could spread the fear (strangely they weren't too upset about how it turned out).

The point: It's alright to let the players think something is invincible when it's not, even if it's near to it.  If they insist on doing something dumb, well then...

[Mystic]

My Deadlands ground had, I think, five definitions for "Dead".

"Absolutely Dead" involved confirming the body and using acid, IIRC.  Even then, they worried, however.  But that's Deadlands.

Shadowrun, never consider the opponent dead until their body has been cut up and fed to the Ghouls.  And even then, expect family to be really slotted off.

Especially if the family is "da family".