[Suicide Junkie]

Best would be an algorithm which checks new addresses against the list before even putting them in!
Keep N small in the first place, and there's less trouble later.
Each submitting machine could keep a filter list of the Last couple submissions so as to cut down on the work the main server has to do.

If you had a sorted list, then the duplicate checking would be really easy.
Decent insertion routines would help a lot too.
Bucket sort to servers holding a piece of the list, then insert using your favorite routine.

Get the n^2 work done as it drips in, so you have years to spend on the problem, instead of rushing it just before trying to send emails.