I already sent you a private message indicating that I think you will need to go with dedicating hosting or with an alternate SMTP server. However, I had another thought. Many have a limit of a certain number of emails per hour. Hostgator has a publicly established limit of 200, but if you call them and talk to them they will up your limit to 400. If you then throttle your email list so that it only sends 400 per hour, you should be ok, as long as you are ok with having your 5000 emails go out over a 12 hour period.
Drupal777