I covered this somewhat in my other comment, but I think here you're thinking about external / internal classification. By removing a voxel, you are changing the voxels around it into 'edge' voxels (if they weren't already). This should boil down into 3 actual cases (symmetry gets you the rest of them) - in the example below the numbers are the group IDs, the - is the voxel being removed
11 2
1- 1- 1-2
The first case is trivial - it's a corner, but the voxels above and to the left remain fully connected through the other voxel.
The second case: it's a corner and the removed voxel has disconnected the above and left voxels that were previously connected
The third case: it's a line, and the removed voxel has disconnected the left and right voxels previously connected.
If you identify that the 2nd or 3rd cases have happened, you need to do some path-finding to see if 1 and 2 are still connected through their other adjacent voxels.
You can get some efficiency here though. If a voxel is entirely internal to a group (i.e. all 8 of its neighbours are part of the same group), then it can be discounted. Why? It's a topology thing. Imagine the 2D case - there are only two possibilities. Either there is a single edge which, regardless of how it twists and turns, still forms a ring of voxels. Or, there are two rings, one containing one voxel, and one containing the other.
E.g.:
xxx xxx
x x-x x
xxx xxx
or
xxxxxxx
x x
xxx xxx
x-x
xxx xxx
That should extend to 3D as well, except instead of a boundary ring, you'd have a boundary surface. So when you are trying to determine whether the two recently disconnected voxels are still connected, you can exclude all the internal voxels from your traversal, because by definition if a voxel is connected to any one of the boundary voxels of a group, it is also connected to all the internal voxels in that group.
It's sort of the reverse effect of the hub voxels I talked about in my answer to the other question - you don't have to find your way from every voxel to every other voxel, you only have to find your way to the interesting voxels.