I think moritz is correct about getting the mailserver to do this throttling for you. But I do have limited experience with problems much smaller than yours. I send out mails to users whose mailboxes are full. I use two strategies to prevent overloading my already overloaded mailserver.

First, it refuses connections and new RCPTs when it's already sweating. Second, I try not to get it to that point. (This send_mail function is from my own Net::SMTP::OneLiner.)

# This part is a no brainer and your mail software
#   likely already supports something like it:

eval { send_mail('postmaster@mei.net', "$dir_entry\@mei.net", 
    "Usage Notice (full mailbox)", $msg) };
if( $@ ) { 
        warn "sleeping for 2 seconds then retrying due to send_mail() 
+WARNING: $@";
        sleep 2;
        redo RETRY;
    }
}
[download]

The second thing is to simply wait until the load average is low enough:

sub sleep_until_low_load {
    my $limit = shift;

    REDO:
    open PROC, "/proc/loadavg" or die $!;
    my $line = <PROC>;
    my $load = $1 if $line =~ m/^\s*([\d\.]+)\s+/;
    close PROC;

    if( $load > $limit ) {
        print "\tsleeping for 5 seconds since $load > $limit\n";
        sleep 5;
        goto REDO;
    }
}
[download]