To clarify I have an app that notifies users via email when certain actions take place (I am not spamming as the user has opted in to the notifications and can change that option at any time). Because of number of emails that needs to be sent, Gmail, Yahoo, etc will not work. Unless I am mistaken services like MailChimp, Lyris, etc will also not fit this need since every email is sent one at a time and is very specific to the user and action that took place.
What I really want is something that would allow me to be able to call some mail function, give it a recipient, from, message and subject, and not have it be blocked by the email service. This can be a free or paid service. I have server access so I can install something if necessary as well but I don't know much about email services and fear if I do it myself, I'll get blocked by some other player like my VPS host or ISP or something.
For my server setup I am currently running CentOS on Linode.