tedster - 9:07 pm on Dec 23, 2011 (gmt 0)

According to the help files for the sitemap_gen.py Python sitemap script, the only URLs added to the sitemap from the access logs should be those that got a 200 response:

When reading access log entries, the sitemap generator will include in the sitemap only the URLs that return HTTP response status 200 (OK). It is thus necessary, in order to avoid inclusion of non-existent URLs, to have a website set-up that will return 404 (not found) HTTP response status for non-existent URLs, not a redirection to a page returning HTTP status 200 (OK). [smart-it-consulting.com...]

So it still sounds like a config problem to me - either that your your server is not sending a true 404 status in the http header but only a "404 page" with a 200 status.