I think Ted's Nuke Anything plugin is one of the most innovative mozilla plugins out there. Without looking at the source at all, I can only assume that it works by way of walking around the DOM tree, setting things to display: none when asked.
I plan on digging around the code sometime and making one or two changes. A 'history' of deletions would be useful and not impossible if this DOM-tree walking was the case: We could maintain a seperate tree as an edit history, or something.
Also of interest, would be explicitly marking the thing you have selected to remove. Consider: you click on an element (such as part of an advert). It gets a 4px solid red border. You decide you want the container-item (a different element relating to the advert), a button controls lets you jump to the parent element which gets the border instead. Also of use when you want to remove an invisible table cell or something. Similar to the way XML Mind's editor works.