Aizatulin

Here is one way which should work:
for each edge (point pair) -> get both half edges -> get both prims (for each half edge) -> get all vertices for each edge point -> find for each prim the corresponding vertex for each vertexlist -> now you have two vertex pairs for each point containing the vertices of both prims -> now you can compare the vertex normals and if the angles of both pairs are greater than a threshold value put the edge into the group.

fuse seems to fix this problem

Sure ,

and yes you are right, you can't use this method if you have any geometry which which has open parts like a plane. You can't use boolean operations aswell. Shooting rays to multiple directions can be an option, but depending on the siuation, this method can also fail, if you have thin holes for example (where is low chance a ray will hit).