If you have unique id assigned to each of your addresses you might consider creating doing the following:
1. script send messages to 300 users (just an example number) starting from the very first from your base
2. script outputs the id of last user to a file (e.g. lastuser.php)
3. after 1 hr go to step 1 and repeat starting from the id read from lastuser.php
The solution might increase your server load a bit but that's not an issue since the database is relatively not big and requests are made only once an hour.
P.S. PHP gurus, please, don't kick me
It's just a try