I was having similar problems, and I just finished my mass mailer (Not spam, but for company newsletters..)
Anyway, what I did was pretty much how some of the previous posts here stated..I grabbed 40 emails from the sql database, mailed them out, and then had the browser automatically refresh the webpage once they sent. (I used javascript for that. was 1 line..real easy)
I then stored a file on the ftp (in a secure directory) that basically kept count where I last left off. Each time the page would reload, it would look at the value in the text file, and then call the
$MyArray = mysql_fetch_array($result);
the amount of times to "get the database back up to where it left off".
Interestingly enough, this script ran fairly well, had no lag or anything otherwise undesirable, and we used it to send our first batch of mail to 5,000 people.
The only problem, of course, is the time it took to do this.. If you have thousands upon thousands of mails, it's going to take a while to complete the operation. I created a little percentage bar, and had it update each refresh of the webpage.. Just let it run a few hours, overnight, whatever, and then you're good to go.