I'm using WP SEO 1.1.6 over WP 3.3.2 Multisite with 4 sites, hosted in a VPS powerful enough to handle it, so hardware resources are off the table.
One of the sites only has a few pages, the second one has about 500 posts. But the other two have about 4,000 and 8,000 posts respectively.
When I activate the XML sitemap feature in the sites, my server gets flooded with lots of heavy MySQL queries which eventually take it down.
Before deactivating sitemaps permamently, I'm trying this approach, I'll let you know if it works.