Email Issues from Perch Site

I have a client's site that appears to be failing to send an email to the client, their user credentials being an example. I've tested using my email address and the email sends, hence I just assumed it was something "their end".

The client has contacted their hosting provider (123reg) and this is their response:

I've looked again through our logs and it seems the messages do not reach our server.

So I'm at a loss as to what to try next?

Below is the Diagnostic Report in case it sheds any light on the situation?

Perch: 3.1.1, PHP: 7.0.29, MySQL: mysqlnd 5.0.12-dev - 20150407 - $Id: b5c5906d452ec590732a93b051f3827e02749b83 $, with PDO
Server OS: Linux, cgi-fcgi
Installed apps: content (3.1.1), assets (3.1.1), categories (3.1.1), perch_blog (5.6.1), perch_forms (1.11), perch_mailchimp (3.1), perch_twitter (4.0)
App runtimes: <?php $apps_list = array( 'perch_forms', 'perch_blog', 'perch_mailchimp', 'perch_twitter' ); ?>
PERCH_LOGINPATH: /perch
PERCH_PATH: /var/www/vhosts/pearsonchange.co.uk/httpdocs/perch
PERCH_CORE: /var/www/vhosts/pearsonchange.co.uk/httpdocs/perch/core
PERCH_RESFILEPATH: /var/www/vhosts/pearsonchange.co.uk/httpdocs/perch/resources
Image manipulation: GD Imagick
PHP limits: Max upload 8M, Max POST 16M, Memory: 256M, Total max file upload: 8M
F1: 3b606135b33e6a102526838f4152a807
Resource folder writeable: Yes
SCRIPT_NAME: /perch/core/settings/diagnostics/index.php
REQUEST_URI: /perch/core/settings/diagnostics/
DOCUMENT_ROOT: /var/www/vhosts/pearsonchange.co.uk/httpdocs
HTTP_HOST: www.pearsonchange.co.uk