Speed issue happen when sending message emails to users email address, not when sending message. Most of the host does not allow bulk emails, most of the time they have limit per hour.

It is better if you send announcement as that will queue email sending and send in interval. Department can go to Front-End page (where [front-end-pm] shortcode is) and click “New Announcement”.

Let me know if it works for you.