GaryK is correct, assuming you are using SMTP delivery via a 3rd party host, in which case you might also use the smtp class from PHPMailer, which makes it much easier to manage this.
If you are using local mail delivery (your mail is sent by the same server that your code is on) things are typically much more efficient.
In my experience, you can push out <1k messages via SMTP mail() just fine on most servers. Over this it is worth looking at other forms of delivery. For mail which is locally handled, I'd say <5k, but do put a usleep or similar delay into the processing to keep server load down - I usually divide out the customers by the acceptable send time (e.g. 3k customers and I'm happy to wait three hours = 0.28s each mail, so insert about 0.2s sleep).