[Sabertooth]

No, Gandalf was quite mortal. He died of physical injuries and his fea passed out of the world, just like any other adan. He was a durable chap, probably moreso than any Elf, but when it came down to it he received the Gift of Men.

Disagree. Gandalf was Maia, and was therefore immortal. Being immortal didn't preclude him from being killed however, as was also true of the elves.

[Caesar Soze]

All fear in Arda were indestructible. Im/mortality is determined by what happens to that fea when it is unhoused. The Valar (and presumably the Maiar) were bound to Arda as a condition of their entrance; thus they are immortal. Elven fear are also bound to Arda. Both Ainur and Elves are capable of constructing or receiving from the powers of Arda new physical forms.

The fear of men, however, leave the world upon the death of their bodies. They cannot be rehoused within Arda without special permission from Eru. That's exactly what happened to Gandalf the Grey when he died, therefore he was mortal. The fact that he was sent back into Arda by Eru until his task was completed further suggests that, after the War of the Ring, Gandalf the White fully expected to die and leave Arda again. Makes the Valarin debates over which Maia gofer should be sent into Endor take on a rather macabre tone.