I don't know if this is the most practical method but after trying a few different ideas, this is what I have found to work flawlessly for quite a while now:
I build the list of email addresses to send to and then send blocks of 500 BCC's at a time. This doesn't mean the page reloads after 500, but that you send a mail() call each for every 500.
block 1
TO: newsletter@site.com
BCC: email1, email2... email500
block 2
TO: newsletter@site.com
BCC: email501, email502... email1000