I’ve had a closer look at this and in my case this is caused by the crawler not re-reading the sitemap. It reports 404 errors for URLs that were actually removed from the sitemap but still in some buffer.
When asking webmaster tools for the referring pages, it reports an XML and when I opened the XML, it did not contain the URL anymore.
I don’t know if this can be solved by updating the plugin.