Cannot modify header information following page not found error
Please note that there are a lot of things that can cause this, and it's very hard to say what goes wrong depending on your system. But the following seems the most plausible:

The page is deleted, so drupal immediately serves a cached 404 page (with 404 header). Some other module which perhaps invokes a wrong hook, then tries to alter the output or output header. Which it can't because the page is already compiled. 

You could try to read the headers of a regular page and one of a 404 page to find out what header is missing (and thus what module might be causing it) I use Fiddler to post such requests and read the server's response, but there are plenty of other tools. 
You could also try to read the issue queues of the modules you use, try to find if someone else ran into this problem earlier. 

As a last resort you could start disabling your modules and try to find when it stops. Or use 'find in files' to see if there are modules calling 'drupal_send_headers'.

But then again, it might not even be a module... 

Please note that a theme is also capable of editing output, and thus might be causing this.