You might need to give more specs on the server to get better replies.
ie, Win vs Lamp.
What are you using for mail on there, are you using a control panel (if so, which one)?
I don't really have an answer, but an curious to replies, as I am also providing hosting to my clients as well. (Lamp, default cPanel setup)
PS. I got delayed in hitting submit, and Gordon had posted before I submitted, off of his link, I found the second result "Limit max emails per hour (cPanel)" useful, mainly the reply by "Vertigo". I am trying those on my server.