Please note that in not.working.dot the watermark is defined three times - one for every header type - first page, odd, and even. You are removing only the wateramrk defined for the first page. Don't use break; in your code and it will be able to remove all three watermark definitions successfully.
The reason for that is that when you obtain NodeCollection, even a "not live" one, all matchings nodes are not prefecthed . They are retrieves from the document on demand. So when you delete a current node and attempt to iterate to next one, especially using iterator, you go nowhere after the first node.
The "live" or "non live" just determines whether the cache of prefetched nodes is flushed when document is modified.
I know its a bit complex, but that's the best we can do to provide a flat view of a tree.