One thing you can do is defer the deletion of vertices.
Replace a "removed" vertex's data with NAN values, but leave it where it is, and record its index in a separate small collection of "open slots".
Any triangles referring to the removed index will be discarded by the GPU, because of the NANs propagating through the rasterization calculation. But you can also swap such triangles with the last valid triplet of indices in the list to get a contiguous buffer of only valid triangles without shifting the entire array down, and that way you don't send invalid ones to the GPU at all.
There is a small overhead to this, due to storing/transferring "dead" vertex data that's not going to be used, but if you're already pushing 10 k vertices and only deleting dozens or hundreds at a time, this probably won't impact the performance significantly.
Whenever you want to add new vertices, you can check the "open slots" and overwrite them with the new vertex information, inheriting the old unused index. Just make sure you've cleared out any triangles that were referencing the unused vertex, if any.
If your open slots list ever exceeds a threshold size, you can then take the time to re-optimize your mesh data (potentially on a background thread), shifting down the valid vertices to consecutive indices and rebuilding the indices array to match. The advantage is that you don't need to do this eagerly with every small change if they're frequent, and you can continue using the old up-to-date but slightly-less-than-optimal version while you wait for the background process to clean it up, instead of stalling your core update loop every time the mesh is edited.