I think we need to distinguish two cases here:

1. The simplest black hole solutions in General Relativity are eternal black holes in vacuum. Yes, you read that right: There is no mass and yet they live forever (and have lived forever). There is no way to say why that is other than: The field equations permit these solutions, so they are possible (at least in principle).

The thing is: Nothing in the field equations says there has got to be matter for your spacetime to have curvature. The spacetime just has to fulfill the equations. If you set the energy-momentum tensor in the equations to zero (i.e. there is no matter), you end up with the equation Ric = 0, where Ric is the Ricci tensor, and it turns out that this equation has non-trivial solutions. "Non-trivial" here means: Non-trivial curvature (i.e. not flat) and/or non-trivial topology (e.g. not infinite volume like 4D Minkowski space).

For instance, apart from the curved black hole solutions, you could also have non-trivial flat solutions with the topology of a 4D torus/donut, i.e. with a finite volume.

Why do these solutions exist? Well, because each of them fulfills Ric = 0. Put differently, your question basically amounts to asking "Why do spheres exist if there are planes?" (Both are the solution to the 2D equation k = 0, where k is 2-dimensional (sectional) curvature.)

-- Intermezzo --

Let me approach your question from a slightly different angle: You are understandably surprised that vacuum black hole (i.e. curved) solutions exist because you associate curvature with gravity and have learned that curvature comes from matter ("matter curves spacetime and curvature is gravity"). But this only have the story:

No one ever said that curvature has to come from matter. What's more, gravity is a very narrow, human-invented term that comes from pre-relativistic times when apples were falling from trees. See, the fundamental thing about General Relativity is not that matter curves spacetime or gravity is curvature but that

1) the universe is a 4-dimensional object ("Lorentzian manifold" in math speech) which fulfills the Einstein field equations and which we call spacetime, and that

2) in the absence of other forces (i.e. in free fall), objects follow the equivalent of straight lines ("geodesics") in that spacetime.

In this sense, even the flat vacuum (Minkowski space) has "gravity": It's just very boring gravity because the geodesics are actual (Euclidean) straight lines: An object will stand still in 3D space and only move in time.

In short: Gravity doesn't care about the spacetime being curved or non-curved. It's always there. It's just that in human, practical terms, we call one situation (falling down from a tree) "gravity" and another one (standing still in empty 3D space) "absence of gravity" but from the perspective of General Relativity there is no real difference: Both are spacetimes with geodesics.

So is it surprising that there are curved spacetimes without any matter in them? I don't think so.

-- Intermezzo end --

Back to our eternal black hole solutions in vacuum: As I mentioned, not only do they live forever but they also have lived forever, so there are not exactly great models for reality as we have yet to encounter a black hole that's ∞ years old.

This brings us to the second case:

2. In realistic models of black holes (i.e. black hole formation) we don't really know what happens to the matter once it passes the event horizon. General Relativity predicts the matter will hit the singularity in finite time ("finite proper time") but in reality we have no clue what happens there.[0] Maybe it vanishes, maybe it does another thing entirely (because of quantum-gravitational effects or who-knows-what).

So I'm not sure I would go as far as saying once a black hole has formed, the situation is similar to one of those vacuum black holes where there's no matter whatsoever. (So I'm not sure your question applies here.)

But even if the situation is similar: We have learned in part 1) that spacetime can be curved for no reason.

Besides, as I mentioned elsewhere[1], in certain situations we can associate with curvature a mass, even if there is no matter present (i.e. we're in vacuum). So I think this answers your other question:

> If the blackhole is then a vacuum, surely it has no mass

Yes, it does!

Anyway, this means another possible answer to your question, why vacuum black holes (in theory) exist, is: They themselves have mass (in the aforementioned generalized sense) and therefore sustain themselves and their curvature.

Hope that helps!

[0]: https://news.ycombinator.com/item?id=34904790

[1]: https://news.ycombinator.com/user?id=codethief