I don't think you're missing anything. Either the vertices are shared and so primitives get subdivided that way, or your data structure says these two vertices are shared (same x,y,z, different anything else) and your algorithm marks the primitives with that vertex in for subdivision also.
It's not easy at all to avoid the cracking/holes caused by shared edges between patches.
Jim