Can you explain why, with a list of 5,000 you feel the need to mail more than 500 an hour? And the timing of the mailing is done in phplist. I've not heard of a hosting company limiting you like this...who is it?
Also, if velocity is your aim:
http://www.volomp.com/