Also, take the hint from Google's sitemaps program online. They like to see real 404 error pages, not re-directs.
We had a redirect that sent all error URLs on our site to the main page, but Google does not like that. So when in Rome...
Sitempas would not let us get past the verification stage until a random error URL which they generate produces a true 404 result instead of a 301 or 302 or 200 result.
Very strange requirement, but if you look at all the big names like CNN, Google, Yahoo, and try a bogus URL on their site, you get a real 404 error page. That's the preferred method of having your house in order according Google.
So moral of the sotry, use a header checker tool, and verify your home page spits out only a 200 code, and that your errorn URLs all spit out a 404 code, and pop up an error page, preferably with navigation on it.