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).
Best Answer
Actually, before you got to the Schwarzschild radius, the pressure previously supporting the neutron star against its own gravity would no longer be able to do so, and the entire star would violently collapse. Some matter would be thrown out, while the rest would become a black hole. The singularity at the center would be among all the rest of the singularities at the centers of all other black holes for the densest objects in the Universe.