from my limited knowledge of the 2.5D code base it seems the problem is the lack awareness of the model. There faces are treated as wires and edges and the area is projected downwards on the the z plane and the normal is upwards.
If you want quick hack, how about a boolean property "project up ", which inverts the normal. That's quick and easy and would probably fix this situation. It would require a simple user interaction when this happens to get the correct paths.
Longer term the fix really needs to be model aware in some way to know what is the inside of the volume. So either some info from the model needs to be passed forward or something like the opencamlib calls, used in your excellent 3Dsurface tools, are needed.
This situation is a persistent problem with the 2.5D tools, as you know. Maybe it would be worth adding something to Part Design to add a normal to the geometric data indicating which side is air and which side is solid. Just a thought. Working backwards to recover this info is very computation intensive and essentially a waste of time since we have this info in the model.
It seems to be a significant thing slowing the the 3D tools too.