So I have been debugging the code:

$message = sprintf(__('Username: %s'), $user->user_login) . "\r\n\r\n";
$message .= __('To set your password, visit the following address:') . "\r\n\r\n";
$message .= '<' . network_site_url("wp-login.php?action=rp&key=$key&login=" . rawurlencode($user->user_login), 'login') . ">\r\n\r\n";

$message .= wp_login_url() . "\r\n";

wp_mail($user->user_email, sprintf(__('[%s] Your username and password info'), $blogname), $message);

If I remove the $message variable from wp_mail() and replace with with "hello" it sends fine, but if I use the message variable, I get no errors, it claims to have sent, but never actually gets sent.

What causes this, and how can I fix the $message variable?