Given your needs, a VPS is more likely to be a better fit (though not a good fit for your budget). Otherwise you'll have to find a host willing to up/remove those limits like your current one did, and such a provider won't be all that easy to find.

Either that, or carefully throttle the emails sending, to stay under the limit the provider has in place.

BTW, why don't you stick to your current host? they seem to be pretty accommodating.