Well, I don't think anything immortal can withstand extreme situations and live every time. I think immortality merely indicates that age can never kill the person. But outside forces could.

This would be Agelessness.

Immortality in the most genuine meaning of the word can only achieved by means of magic that doesn't adhere to the laws of physics, which mark the heat death of the universe as pretty much the end for any consciousness science can describe.

Immortal - Time has little to no effect on the being. However you can kill (With great effort typically) a immortal. Phoenixes are said to be immortal after a fashion but they die, they simply rebirth.

Invulnerable - Time does have a effect on you but most of the things that would normally snuff you out, don't. This is kept in check by the 'level' of how Invulnerable you are. Take Superman, he's a nigh-invulnerable being, but magic and as we all know, the charged elements of his homeworld weaken him a great deal and can kill him. With a invulnerable being, you can simply wait long enough and age will get them.

I doubt something's truly immortal if it can be killed, since "immortal" translates to "can't die".

See, the thing with immortals is that they always have some kind of curse or weakness that ENDS the immortality. For example, a vampire is immortal...unless you stab that sucker with a wooden stake through the heart. Many other kinds of immortals have such a weakness. Aside from that one, usually obscure, weakness they are impossible to kill. Some movies are centered entirely around figuring out that weakness while avoiding death; many horror movies for example.

On a side note, one of my favorites is seen in, The League of Extraordinary Gentlemen, a fantasy/action movie.

All this talk about Immortality reminds me of the movie blade.
Vampires Immortality in that move means if you get a paper cut from silver, or a flashlight in your face, you will die.
I'll rather be mortal, thank you...