How to change “Registration complete. Please check your e-mail.” in wp-login.php

After wp-login.php figures out what error messages to display, the $errors object gets passed through the wp_login_errors filter:

$errors = apply_filters( 'wp_login_errors', $errors, $redirect_to );

When that error message is added to the list of “errors”, wp-login uses the code 'registered', which you can use to narrow down your search.

So something like this should do it (untested, but this is the basic flow of the code):

add_filter( 'wp_login_errors', 'override_reg_complete_msg', 10, 2 );
function override_reg_complete_msg( $errors, $redirect_to ) {
   if( isset( $errors->errors['registered'] ) ) {
     $needle = __('Registration complete. Please check your e-mail.');
     foreach( $errors->errors['registered'] as $index => $msg ) {
       if( $msg === $needle ) {
         $errors->errors['registered'][$index] = 'Your new message';
       }
     }
   }

   return $errors;
}