Let me start with your question about stability: Any astrophysical object is subject to a battle between two forces: gravity (which will try to collapse the object) and whatever force prevents that collapse. A regular star uses heat (generated by thermonuclear fusion) to counteract gravity. When it runs out of fuel, gravity begins to compress the star further. Here are three different possible end states: a white dwarf, where the degeneracy pressure between electrons (that is, the Pauli exclusion principle as applied to electrons) is sufficient to balance gravity; a neutron star, where the degeneracy pressure between neutrons (that is, the Pauli exclusion principle as applied to neutrons) is sufficient to balance gravity; or a black hole, where there is no force/pressure that is strong enough to counteract gravity, and all the matter collapses (in classical GR, to a point/singularity) under gravity. The white dwarf and neutron star are stable unless they grab too much mass from somewhere else.
As for the rest of your question, it depends on what you mean by a black hole. Are there regions of space from which no light can escape (trapping horizons)?: almost certainly. Supermassive black holes can have large horizons, with surprisingly small space-time curvature, and we understand gravity and GR well enough that we can be reasonably sure that such horizons exist. Are there singularities inside these horizons? - almost certainly not. Physicists dislike singularities, which is one reason why they search for a quantum theory of gravity. So the question of what lies inside a black hole can only be answered when someone comes up with a consistent quantum theory of gravity.
We know enough about electron physics to suggest that there is a limit (the Chandrasekhar limit) to how massive a white dwarf can get, and similarly we know enough about neutron physics to suggest that there is a limit (the Tolman–Oppenheimer–Volkoff limit) to how massive a neutron star can get. Beyond this our knowledge of states of matter is shaky, so yes, there could be a quark star or some other exotic state of matter whose degeneracy pressure can counteract gravity. But the general trend is that there is a limit to such forces, and that for a sufficiently massive object there is no way to stop complete gravitational collapse.
Observational evidence for black holes typically comes down to: we know that there is a massive object in this region of space (by looking at the objects that orbit around it), and we know that it packed into a volume of space that is at least this small (by looking at accretion disk data, for example). The density we compute from that mass and volume is too high for a neutron star, so in the absence of evidence for various exotic stars/states of matter, we shall assume it is a black hole.
EDIT: As noted by the commenters below, the density (Mass over Volume) for black holes can be quite low; it is more accurate to say that the Mass to Radius ratio becomes too high for it to be anything but a black hole (i.e. all the mass is contained within the Schwarzschild radius, and so it undergoes gravitational collapse).
The phrase black hole tends to be used without specifying exactly what it means, and defining exactly what you mean is important to answer your question.
The archetypal black hole is a mathematical object discovered by Karl Schwarzschild in 1915 - the Schwarzschild metric. The curious thing about this object is that it contains no matter. Techically it is a vacuum solution to Einstein's equations. There is a parameter in the Schwarzschild metric that looks like a mass, but this is actually the ADM mass i.e. it is a mass associated with the overall geometry. I suspect this is what you are referring to in your second paragraph.
The other important fact you need to know about the Schwarzschild metric is that it is time independent i.e. it describes an object that doesn't change with time and therefore must have existed for an infinite time in the past and continue to exist for an infinite time into the future. Given all this you would be forgiven for wondering why we bother with such an obviously unrealistic object. The answer is that we expect the Schwarzschild metric to be a good approximation to a real black hole, that is a collapsing star will rapidly form something that is in practice indistinguishable from a Schwarzschild black hole - actually it would form a Kerr black hole since all stars (probably) rotate.
To describe a real star collapsing you need a different metric. This turns out to be fiendishly complicated, though there is a simplified model called the Oppenheimer-Snyder metric. Although the OS metric is unrealistically simplified we expect that it describes the main features of black hole formation, and for our purposes the two key points are:
the singularity takes an infinite coordinate time to form
the OS metric can't describe what happens at the singularity
Regarding point (1): time is a complicated thing in relativity. Someone watching the collapse from a safe distance experiences a different time from someone on the surface of the collapsing star and falling with it. For the outside observer the collapse slows as it approaches the formation of a black hole and the black hole never forms. That is, it takes an infinite time to form the black hole.
This isn't the case for an observer falling in with the star. They see the singularity form in a finite (short!) time, but ... the Oppenheimer-Snyder metric becomes singular at the singularity, and that means it cannot describe what happens there. So we cannot tell what happens to the matter at the centre of the black hole. This isn't just because the OS metric is a simplified model, we expect that even the most sophisticated description of a collapse will have the same problem. The whole point of a singularity is that our equations become singular there and cannot describe what happens.
All this means that there is no answer to your question, but hopefully I've given you a better idea of the physics involved. In particular matter doesn't mysteriously cease to exist in some magical way as a black hole forms.
Best Answer
I'm no expert but there is a mechanism that causes black holes to lose mass called Hawking radiation. To understand it, there is a thing in quantum mechanics called the uncertainty principle that basically means that if you know the exact (or nearly exact) position of a particle then you can not know the momentum of that particle to the same degree of accuracy, this then means that a particle can not be totally still, because if it was, you could know the position and the momentum, which would be zero. Since particles are excitations of quantum fields, this means that the fields can not be exactly still either and therefore have to "ripple" a bit, therefore causing excitations and therefore particles to be created. These are called virtual particles and they are always created in pairs (one particle and one anti particle). When they are created, they move out from each other semi-elliptically and then curve back into each other, "destroying" one another. This has to happen because according to the universal conservation of mass you can not create mass or energy. So when these particles are created near or basically on the event horizon of a black hole, they move out from one another, but instead of destroying each other one of them is "sucked" into the black hole. This means that the other one has just been left to roam the universe forever. This defies the conservation of mass and means that the black hole has to lose mass equal to the mass of the "free" particle. Over time this output of Hawking radiation will be more than the input of other mass from stars and planets etc. and therefore cause the black hole to evaporate. So a straight forward answer: No, black holes are not immortal.