連関エンティティに相当するテーブルで、

MYSQLは詳しくないのですが。

ＭｙＳＱＬ　【定義命令】CREATE TABLE

によると、MYSQLは一時テーブル使えるらしいので、

create temporary table Select ～

で、一時テーブルを作成して、それとJoinすればとりあえず可能じゃないかと思います。

スマートかどうかは別として。

同じフィールド構成のテーブルを作って、

Inser Into 仮テーブル Select Distinct *

で必要なデータだけ取り出しておき、元のテーブルからは全レコード削除、Indexをつけてから仮テーブルからデータを戻す。

データを戻したら仮テーブルはDropしましょう。

考え方としては、サブクエリの結果を一時テーブルに保存して、サブクエリのかわりにその一時テーブルを使うわけで、サブクエリでできるなら一時テーブルでもできるはずです。

とりあえず、私はMysqlあまり知らないのですが、

MySQL :: MySQL 4.1 リファレンスマニュアル :: 6.4.5 DELETE 構文とか

MySQL :: MySQL 4.1 リファレンスマニュアル :: 6.4.2.3 ANY、IN、SOME とともに使用したサブクエリ

を読んでみたら、↓の方法でいけそうな気がするのですが…。

create temporary table temp_fordelete
Select 
max(bookmark_tag_id) as maxid,
bookmark_id,tag_id,count(*)
from bookmark_tag
group by bookmark_id,tag_id
having count(*)>1

で削除対象のIDを一時テーブルに保存。その後

delete from bookmark_tag
where bookmark_tag_id
 in (Select maxid from temp_fordelete)

でそのIDに該当するデータを削除