6. Most sitemap software times out/runs out of memory before the sitemap can
be completed.

I'm presuming 1) you've styled your sitemap generator after the samples in G's webmaster tools, and 2) you're requesting the generator from a browser?

Have you tried/have the ability to run a program from the command line? This is the best solution, really. It would probably be fine if you can.

If you can't, the way I get around timeouts where it has to be requested from a browser is to use fork(). Fork is pretty simple in concept:

if $pid = fork() { &parent_process; }
else { &child_process; }

When initiated, a child process is started - this is your sitemap generator. A process id is assigned to the child process and if it exists, the parent process - an immediate response to the browser "job in progress" - is returned.

However, you have to be careful. If you don't understand fork, the parent process can hang waiting for the child to finish, or the child may exit prematurely. One way to approach this is to close the STDOUT filehandle when starting the child, and make the program wait for the child before exiting:

if $pid = fork() { &parent_process_do_not_exit; }
else {
close (STDOUT);
&child_process;
}
waitpid($pid,0);

The above is perl code, but equivalents can be concluded in any server side language.

I totally understand your comments and agree.  We have used fork() on several processes, but the server host has now blocked command line access and even system command acccess from inside PHP because of server loading issues.  We have heard of software available that will map these large sites without all the memory and system resource useage.  This is what we were trying to find.

I really just need to buy a dedicated server so I'd have full control. Until then, I'm trying to find something to get by.

Thanks for responding! Any other thoughts are appreciated.

I have written my own and it handles well around 980K+ URLs. I use cron and submit sitemap every six hours. Though memory consuming due to lots of SQL usage but my site updates every minute

anything you can do to decrease load times for your site will allow google to spider more of your 3rd level pages.
in some cases you can get some efficiency with cacheing or serving compressed content.