Am trying to help, but you must check things suggested and share back findings - other wise, we are guessing and could be taking you down rabbit holes that lead nowhere! Don't wanna do that!
Moodle isn't a mail server. Without any SMTP configuration it will try to use Sendmail and uses PHPMailer to build messages. Once a message is built and moodle tries to send, that's all that moodle can do. The speed of delivery is now up to Internet ... number of devices (routers/switches/email gateways) that message has to go through to get to the destination.
And that's another factor ... student A uses @jaboynk.com for email. Where on internet is that mail server? 2 hops away from your moodle? or 20 hops away from your moodle? UNKNOWN.
"the task of sending a message to two people takes at most 30 seconds"
That could be due to the SMTP setup is on the same network (fewer hops away from the moodle server) thus faster.
"its new configuration takes 5 minutes"
New server is on a different network. Not using the same SMTP service/setup?.
I suggested you check SMTP setup. Did you?
There is a plugin which might help
https://moodle.org/plugins/local_mailtest
Install the version that matches your core version.
The cron job/task, if delayed too long, gets qued up in adhoc_task thus the suggestion of setting the path to your php-cli so you could go to the task list and find the task for sending mail, and click the run now link to view how that mail is being processed locally.
With this issue, there is not ... and never will be ... one set of instructions to fix. Too many factors to begin to guess.
'SoS', Ken