PhpLB has no probs with hostgator infact it is compatible with many hosts. I am hosting PhpLb on both Hostgator and other sites also with no probs till now.
You can try them for just a penny and see if they suit you. Get the coupon here: http://www.hostingdiary.com/2007/09/web-hosting-cou.html Andrew
Just a caution: Do not send more than 200 mails an hour. Your server will be locked for spamming without thorough investigation. (That's just in case of shared server) So not a zero problem solution, but still one of the best out there. I am satisfied with their services and support.
Yes..Same here..No problem..The problem only like ipod say.. they probably locked your account if you have sent more than 200 mail an hour.. I had the problem last week.. This is not problem.. You can disable the email submission..
If you are sending out a large newsletter look into an outside solution from your host's mail. This is an issue with any host.