I think this is another manifestation of the same problem as discussed in this topic, where it arises in a different way:
In both cases there is erratic behavior of whether or not Edges that by all analysis are on a Face do or do not cut that Face. Seems like a hole (pun intended) lurking deep in the logic somewhere.