You'll have to use a VPS for this -- there's no way around it. While the site resources may be small, and it only has 1 site with a few email accounts, it does not matter. It needs more "email resources", and you'll never get that from shared hosting.
The above list, while helpful, is ultimately useless. They all limit email...
...and several of those hosts are horrible.
The other option is to use an SMTP service, such as Mandrill or SendGrid.
- Mandrill is cheap, but is some still spam blacklisted. The first few monthly emails are free.
- SendGrid is a bit more expensive than Mandrill, but the servers are rarely blacklisted. ($10 per 40k emails per month)
-
Amazon SES is horrible -- do not use it. It's cheap, but it's crappy.
The reason for all of this is spam -- nobody wants to have their servers listed. And for only $5-10/monthly, it's not worth the risk (by the host) to give more/unlimited email delivery. You're just not fit for shared hosting, either in whole (site, email, etc) or in part (email needs only).
I'd just spend the $10 to get SendGrid if I were you.
Who's the current host? They should have mentioned this option to you!