In your case I would suggest to go with dedicated type of server where you will have your own IP and mail server so you can send as many emails as you wish.
Such "dedicated" server could be:
- Fully dedicated -- physical server with unique IP where all resources belongs to you. Can be quite expensive.
- VPS (Virtual Private Server) -- few virtual servers can be hosted on the same physical server using virtualisation technology. For you it will look like completely separate server with unique IP where you have full access and can install any software. Quite cheap these days -- often you may find it priced around twice the price of shared hosting (sometimes even cheaper, depends on plan) but with all goodness offered by being in control of all the software you run -- considering the advantages it is well worth it.
- Cloud-based virtual servers (like Amazon AWS or Rackspace Cloud Hosting) -- in short -- you will have virtual server with additional benefits of cloud-computing (you can scale easily -- attach additional storage or computing resources at any time etc).
With your own mail server you will not be restricted by the limits from your hosting company (well, as long as it all look legit - i.e. you are not only sending hundreds of thousands emails with very little web traffic).
Mail sending companies are good for sending mass emails where content is the same for all customers (well, with some personalisation if required) -- they are not that good (if they can do this at all, cannot confirm here) to send frequent emails with completely different content (that was my conclusion when I have researched this moment about a year ago).
Considering that VPS and Cloud-based servers are not that expensive (Amazon even has some Free Usage Tier that you can use to test if it will be good for you) it is definitely the way I would go in such situation. Yes, this may require technical knowledge to setup and configure your own server, but you may go for a Managed VPS (where hosting company will do all server setup and management for you for an additional cost).