I too ran across this last week. Everything looks fine in layout view and even the print preview, but when printing or exporting the mxd a previously deleted graphic reappears in the print copy.
when I was adding the graphic to the drawingGraphicsLayer I was calling drawingGraphicsLayer.add(map.graphics.add(graphic));
so essentially, I was adding the graphic to both the drawingGraphicsLayer and the default GraphicsLayer map.graphics
I think the reason I did this was because I was calling map.addLayer(drawingGraphicsLayer); before the map was loaded which caused a JScript runtime error "this._cg._surface" is null or not an object.