I have the same problem. I’ve tried apache mpm-prefork and mpm-worker, mod-php, php-fcgid, lighttpd and nginx. The best results I got with cherokee webserver, but with 70k+ URLs I stil get 4-6 minutes downtime 4 times a day.
I’ve managed to find a solution fosr splitting the large xml sitemap:
http://www.dyasonhat.com/wordpress-plugins/split-large-xml-sitemaps-php-script/
