Hi,
I have this working fine with Google site maps. Yes there is a fix.
I have found oscommerce does not work very well with search engines. A lot of the search engines are now giving a duplicate content penalty in the rankings.
This means over time as you get a product, category or review not found when removing products you are no longer selling you can get hit with a penalty. Also with having the sort by product name or price this also causes the duplicate content penalty.
The same can be said for my contribution. When a URL can not be found it gets redirected to the front page.
The best method would be to go though the list of cached URL's before anything else loads and give a header("HTTP/1.0 404 Not Found"); if the URL?s can not be found.
You can use this tool to find out what headers your site is showing:
http://www.rexswain.com/httpview.html