I'm using WP Super Cache and also WordPress SEO by Yoast.
Problem is the sitemap is never cached, unless I visit it via a web browser.
On the WordPress SEO plugin code, there's this:
if ( WP_CACHE )
wp_schedule_single_event( time(), 'wpseo_hit_sitemap_index' );
which in turn makes a wp_remote_get call to the sitemap. So either this doesn't occur, or the WP Super Cache plugin doesn't cache wp_remote_get calls?