[Plugin: WordPress SEO by Yoast] Sitemaps don't work on multiple sites

I have had this problem with this plugin for months on multiple sites, but I expected to find the xml sitemap at the location the plugin provides, but I always get 404 errors. Each site is complete different than the others. I have tried non-www and www version and still no luck. It seems to have different URLs for the xml sitemap on different sites too and is inconsistent in terms of what the url is for an xml sitemap. Not sure how to resolve it and have functional xml sitemaps. I am also using W3 Total Cache and a section of the plugin requests the url of the xml sitemaps.

http://wordpress.org/extend/plugins/wordpress-seo/