Hi. I recently migrated from a dedicated to a shared server. The forum sends a lot of emails to members for various notifications, such as new topics replies, New creates topics, etc. and many of them are to invalid addresses. As a result, mailchannela, he 3rd party mail server that the host uses, deferred/blocked the forum from sending emails.

Support said that based on the volume of emails, I should be using a transactional email service. Any recommendations? 

We have sendgrid integration, which may well serve your purposes. You can integrate with this in 

System->Site Features->Integrations