Problem with email_exists in shortcode

I have a custom registration form that I insert into a page via shortcode. The shortcode function looks like this:

function custom_registration_form_shortcode() {

  $error = FALSE;        

  if (isset($_POST["submit"])) {

    //Get other $_POST data here

    $email = is_email($_POST["email"]);
    if (!$email) {
      $error = TRUE;
      $errorMsg = "EMAIL NOT VALID";
    }
    if (email_exists($email)) {
      $error = TRUE;
      $errorMsg = "EMAIL EXISTS";
    }
  }

  if (!$error) {
     // Creating random password, setting username, wp_create_user, etc. working fine
     $output = "GOOD";
  }

  // Some other stuff here that does not set $error to TRUE

  if ($error) {
     $output = $errorMsg;
  }

  return $output;
}
function jogol_add_shortcodes() {
  add_shortcode('jogol-registration-form', 'custom_registration_form_shortcode');
}
add_action('init', 'jogol_add_shortcodes');

What happens is that the user gets registered fine, but it still returns “EMAIL EXISTS” as if wp_create_user gets executed before email_exists($email) or the code runs twice on submit.

I´m going nuts and any help/hints are highly appreciated. Thanks!

UPDATE:
Here´s a stripped down version. No validation. Just for testing purposes.

function registration_form_shortcode() {

  if (isset($_POST["registration_submit"])) {
    if (email_exists($_POST["email"])) {
      $output = "EMAIL EXISTS";
    } else {
      $username = $_POST["email"];
      $random_password = wp_generate_password(8, false);
      $status = wp_create_user($username, $random_password, $_POST["email"]);
      $output = "GOOD";
    }
  }

  $form =
  '<form name="registration" action="'.esc_url($_SERVER['REQUEST_URI']).'" method="post">
    <label for="email">Email</label>
    <input type="text" name="email" value="'.$_POST["email"].'" />
    <input type="submit" name="registration_submit" value="Send" />
  </form>';

  $output .= $form;

  return $output;
}

function add_my_shortcodes() {
  add_shortcode('registration-form', 'registration_form_shortcode');
}

add_action('init', 'add_my_shortcodes');

What I did (and ask you to try please):

1. Put that code in my theme´s functions.php
2. Added the shortcode to a page via [registration-form]

What it should do when I enter a valid email-address that is not already registered with my WP-install and hit the Send-button:

1. Create the user
2. Display “GOOD” above the form

What it actually does:

1. Create the user
2. Display “EMAIL EXISTS” above the form

I have no clue. Any ideas?

This is a basic version of your code above which seperates the registration logic (handled on init) from the form output done by the shortcode.

It will basically work, but is missing any validation so just to show the concept.

$wpse_email_exists = null;

function registration_form_shortcode() {

    global $wpse_email_exists;

    $output="<form name="registration" action="" . esc_url($_SERVER['REQUEST_URI']) . '" method="post">
                <label for="email">Email</label>
                <input type="text" name="email" value="' . $_POST["email"] . '" />
                <input type="submit" name="registration_submit" value="Send" />
            </form>';

    echo $wpse_email_exists;

    return $output;
}

function manage_my_registration() {

    global $wpse_email_exists;

    add_shortcode('registration-form', 'registration_form_shortcode');

    if (isset($_POST["registration_submit"])) {
        if (email_exists($_POST["email"])) {
            $wpse_email_exists = "EMAIL EXISTS";
        } else {
            $username = $_POST["email"];
            $random_password = wp_generate_password(8, false);
            $status = wp_create_user($username, $random_password, $_POST["email"]);
            $wpse_email_exists = "GOOD";
        }
    }
}

add_action('init', 'manage_my_registration');

As you already pointed out yourself in The Loop, the actual problem with your code from the initial question is, that the code runs twice, when other plugins get the content and parse the shortcode.