以前散々悩まされたのでこちらに残しておきます.

追記：セッションのデフォルトの挙動では「排他ロック」がかかるため再現しないようです.

一般的な二重送信対策の流れ

検索サイトで「PHP」「二重送信」などで検索すると検索上位にいくつか見られるように, PHPでの二重送信対策としては一般的に下記のような対策が取られています.
※ 正確には二重送信対策としてだけでなくCSRF対策も含めてこれらの対策が採用されていますが, こちらの記事では二重送信のみに焦点をあてて話していきたいと思います.

二重送信対策処理の概要

フォーム画面で「トークン（推測不可能な文字列）」を発行し, セッションに入れる
- ここでは「トークン」という名称にしましたが, ワンタイムチケットやらなにやら記事によっていろいろ名称が違っています. でもやってることはだいたい同じかと.
- 昔見た記事ではセッションではなくDBに入れる方法もあるとのこと（記事見つからず…）.
フォームのhidden要素として「トークン」を仕込んでおく
フォームの受け取り側で, hidden要素として「POSTされたトークン」と「セッションに入れておいたトークン」を比較する
比較結果が一致していた場合は, DBへ登録などの処理を実行する
- 比較結果が不一致だった場合は不正なアクセス・二重送信とみなして処理を実行しない(エラー扱いとする)

▼参考: 検索サイト上位にあがってくる記事(どちらも少し古めの記事です)
http://chibitcpu.blogspot.jp/2011/11/php22.html
http://www.tecblo.com/programming/460.html

ただ, これだけの処理だと二重送信は完全には防ぎきれないことがあります.

二重送信できてしまう処理とは？

サンプルとしてシンプルな例をあげます.
（このサンプルではかなり省いてますが, 実際にはフォームの値の検証とかもろもろしないとダメです）

フォーム画面側の処理はこちら.

sample1.php

<?php
// セッションを開始する
session_start();

// トークンを発行する
$token = md5(uniqid(rand(), true));

// トークンをセッションに保存
$_SESSION['token'] = $token;
?>

<html>
  <head>
    <title>入力画面</title>
  </head>
  <body>
    <form action="sample2.php" method="POST">
      <input type="hidden" name="token" value="<?=$token?>">
      <input type="text" name="sample_name" value="">
      <input type="submit" value="送信する">
    </form>
  </body>
</html>

POSTされる側の処理はこちら.

sample2.php

<?php
// セッションを開始する
session_start();

// セッションに入れておいたトークンを取得
$session_token = isset($_SESSION['token']) ? $_SESSION['token'] : '';

// POSTの値からトークンを取得
$token = isset($_POST['token']) ? $_POST['token'] : '';

// トークンがない場合は不正扱い
if ($token === '') {
    die("不正な処理ですよ。");
}

// セッションに入れたトークンとPOSTされたトークンの比較
if ($token !== $session_token) {
    die("不正な処理ですよ。");
}

// セッションに保存しておいたトークンの削除
unset($_SESSION['token']);

// ↓ここにフォームで行う処理を書く

// フォームから受け取った値をDBに登録したり...
$sample_name = $_POST['sample_name'];
Sample::insert($sample_name); // DBに登録する処理だと思ってください

?>

ポイントはここ.

フォームで行う処理

// ↓ここにフォームで行う処理を書く

// フォームから受け取った値をDBに登録したり...
$sample_name = $_POST['sample_name'];
Sample::insert($sample_name); // DBに登録する処理だと思ってください

こんな単純な処理なら二重送信は防げるのですが, 処理時間がかかる場合, この処理方法では二重送信を許してしまうことになります.

下記の例ではおよそ3秒程度の間二重送信が実行できてしまいます. 3秒間もあれば送信ボタン連打したりすれば簡単に二重送信できます.

フォームで行う処理

// ↓ここにフォームで行う処理を書く

// フォームから受け取った値をDBに登録したり...
sleep(3); // サンプルなのでここで処理時間を稼ぐよ

$sample_name = $_POST['sample_name'];
Sample::insert($sample_name); // DBに登録する処理だと思ってください

PHPにおけるセッションの保存タイミング

上記の例で二重送信が可能になってしまうのは, PHPのセッション保存タイミングに原因があります.

まず, 例としてあげたようにセッション開始についてはこちらのsession_start関数を使用します.

▼PHPマニュアル: session_start
http://php.net/manual/ja/function.session-start.php

上記であげたサンプルでは, セッションの開始処理はありますがセッションの保存処理は書かれていません.
ではどこでセッションが保存されるのかというと…

▼PHPマニュアル: session_write_close
http://php.net/manual/ja/function.session-write-close.php

セッションデータは、session_write_close() をコールしなくても、スクリプト終了時に保存されます。

こちらにさらっと書かれてますが, 逆をいうと「セッションデータはsession_write_close()コールしなければスクリプト終了時に保存される」ということです.

つまり, $_SESSIONをいくら書き換えても, スクリプトが終了されない限りその間のアクセスでは同じ$_SESSIONの値を参照することになります.

先ほどあげた例では, 「unset($_SESSION['token'])しても, 実際にセッションが保存されるのはスクリプト終了後（= 3秒スリープした後）」ということになります.
残念なことにその間の二重送信は許容されてしまうのです.

フォーム処理に時間がかかる場合の対策

そもそもそんなに時間のかかるような処理をしなければ良い話ではあるのですが, 入力された値のチェックやらなにやらで時間がかかってしまうことはあるかと思います.

そこで, 今回の対策としてこんな風にPOSTされる側の処理を書き換えます.

sample2.php

<?php
// セッションを開始する
session_start();

// セッションに入れておいたトークンを取得
$session_token = isset($_SESSION['token']) ? $_SESSION['token'] : '';

// POSTの値からトークンを取得
$token = isset($_POST['token']) ? $_POST['token'] : '';

// トークンがない場合は不正扱い
if ($token === '') {
    die("不正な処理ですよ。");
}

// セッションに入れたトークンとPOSTされたトークンの比較
if ($token !== $session_token) {
    die("不正な処理ですよ。");
}

// セッションに保存しておいたトークンの削除
unset($_SESSION['token']);
// セッションの保存
session_write_close();
// セッションの再開
session_start();

// ↓ここにフォームで行う処理を書く

// フォームから受け取った値をDBに登録したり...
$sample_name = $_POST['sample_name'];
Sample::insert($sample_name); // DBに登録する処理だと思ってください

?>

追加したのはこの部分です.

セッションに保存したトークンの削除処理

// セッションに保存しておいたトークンの削除
unset($_SESSION['token']);
// セッションの保存
session_write_close();
// セッションの再開
session_start();

これで少なくともsession_write_close()実行時点でセッションが保存されるため, この後の処理がいくら時間がかかっても二重送信を防ぐことができます.

もちろん, このトークンのチェック処理までに時間がかかってるようなら意味がない話ですし, この処理で完全に防ぎきれるわけではないので, PHPだけでなくJavaScriptでの二重送信対策を併用したり, 少しでも元々のフォーム処理を速くできるといいのかなーと思います.

少しでもなにかの参考になれば幸いです.

追記：2015-03-31

コメント欄でご指摘いただきましたように, PHPセッションのデフォルトの場合はこちらの状況は再現しないようです.

デフォルトではsession_start()実行時点で 排他ロックがかかり, 今回掲示したサンプルで連続POSTされたとしても1つめのスクリプトの実行が終わるまで2つめのsession_start()は待ち状態に入るため, そもそも「二重送信」になることはありません.

この記事の「二重送信」を再現するためには, 「セッションの排他制御が無効になっていること」が条件のようです.

※ 参考までに, こちらの記事で動作の検証をしていた時はmemcachedを利用していました.

ご指摘いただき有り難うございました.
セッションの挙動も改めて再確認でき, 非常に参考になりました.

PHPでの二重送信対策が、効いていない？(追記あり)