WordPress mails being sent from @locahost and being rejected

What is the setting in your server /etc/hostname file? Based on wp_mail source code:

if ( !isset( $from_email ) ) {
    // Get the site domain and get rid of www.
    $sitename = strtolower( $_SERVER['SERVER_NAME'] );
    if ( substr( $sitename, 0, 4 ) == 'www.' ) {
        $sitename = substr( $sitename, 4 );
    }
    $from_email="wordpress@" . $sitename;
}

What this means is that the name localhost is pick up from /etc/hostname.