Show us the HTML form that collects the data. You are most likely posting to the same page. It's a good idea to have some kind of conditional that validates the data before posting.

...use a token to make sure you don't process the same form twice.

(This will require you to generate the form itself via PHP, but that's not a bad thing.)

Say, for example, that your current form looks something like this:

  <form action="contact.php" method="post">
      <label>Name: <input name="name"></label>
      <label><textarea name="message"></textarea></label>
      <input type="submit" value="Submit">
  </form>

You'll need to make a PHP page for that HTML form.

  <?php
  // start a session
  session_start();

  // a "token" is just an arbitrary, unique identifier
  $token = md5( rand().$_SERVER['HTTP_USER_AGENT'] );

  // save the token to your user session
  $_SESSION['token'] = $token;

  // add the token to a hidden form field
  ?>
  <form action="contact.php" method="post">
      <input type="hidden" name="token" value="<?php echo $token; ?>">
      <label>Name: <input name="name"></label>
      <label><textarea name="message"></textarea></label>
      <input type="submit" value="Submit">
  </form>

Then, on your contact.php script, check that the token exists and is valid:

  <?php
  session_start();
  if( 
      // if there's a token in the session
      ! empty( $_SESSION['token'] )
      // AND a token in the form submission
      && ! empty( $_POST['token'] )
      // AND the tokens match
      && $_SESSION['token'] === $_POST['token']
  ){
      // THEN, the form submission is legit.

      // first, DELETE the token from the session:
      unset( $_SESSION['token'] );
      // that way, if the user hits the [back] button,
      // the script will ignore the repeated submission
      // because there's no matching token in the session.

      // next, proceed with processing the form submission
      // and sending the email as normal.
  }else{

      // if there's no matching token, 
      // the form submission is a duplicate
      // (or possibly from a really old visit, and the session has expired).
      // so, don't process it or send any emails.

      // you might redirect to the contact form again,
      // or the homepage, or whatever you like.
  }

Edit

there doesn't seem to be any actionable item aka: a submit button.

since the entire <form> is missing from the code sample, I'm assuming that it's on another page and functioning properly. He mentioned that the problem occurred when someone reloaded the page (or, presumably, navigated to it via the [back] button or by accident). @markblackler, does the script email you successfully when you submit the form the first time?

The biggest problem lies in your $mail_status, currently it just checks if it exists / has a value which can include blank values.

$mail_status comes from the call to mail(), which will always be either true or false. It should work as expected.

Can you show me your current code (both scripts)?

It may be easier to share the code on another site (I like making a gist on github) - css-tricks isn't great for sharing code :(

So, you didn't try adding a token to the form yet?

Why don't you share your attempt?

I'll help people all day long, but I don't just do "free work" :p

Edit

have a look. For explanations, see my comment above.

No problem, glad I could help. : )