It's usually best to create just one post and not duplicate in other forums. Leads to confusion for all.
That aside ... is the VPS managed or un-managed? If managed, then provider is supposed to be your first point of contact for technical issues ... minus of course internals to Moodle (which provider probably won't venture into).
Definition: internals to Moodle ... it's config .. such as the values for SMTP relay.
When the site was on shared hosting, had you setup an SMTP relay for mail? or no SMTP and Moodle using built in PHP Mailer?
Moodle isn't a mail server ... it only 'packages' content ... like a forum posting into a 'container' (for lack of a better term) to send via EMail. The actual mailing of that message is handed off to other applications to actually send the mail. Typically, on Linux based systems, those are sendmail, PostFix, or other.
Would help to know what OS your VPS is ... as an example, OS is Linux (Ubuntu or CentOS) ... the server should be keeping a log for mail handled by sendmail or postfix or other .... found in /var/log/maillog Now if on managed VPS, you might have to contact provider (ticket system) to inquire ... ie, check that log.
Checking that log might disclose the issues and thus give information for resolving the problem.
'spriit of sharing', Ken