Ah, you got me thinking now. Is a Graph element a paragraph-containing element? The reason I ask is that a marker has to live in some paragraph, even if it is represented structurally as a sibling to a paragraph. I'm not quite sure of the exact logic, but I do know that if you put a marker as a sibling to paragraph-containing elements, its actual text location will end up within one of those paragraphs. Therefore, if you delete the paragraph element, maybe it will force a delete of the marker element as well.
I don't know this absolutely for sure, and I don't know if this is the problem you are seeing. Just an idea, really.
Russ