Ich habs jetzt mal direkt mit der mysql-shell getestet:
mysql> DELETE g
-> FROM test2 AS g
-> LEFT JOIN tribe AS t ON t.id = g.player_id
-> WHERE t.id IS NULL;
Query OK, 1076528 rows affected (3 min 51.96 sec)
mysql> DELETE FROM test3
-> WHERE player_id NOT IN
-> (SELECT id FROM tribe);
Query OK, 1076528 rows affected (3 min 38.80 sec)
Das sind natürlich keine exakten Werte, da das System nicht extra dafür abgestellt wurde
Im großen und ganzen scheint es mir aber keinen großen Unterschied zu machen.
Auf weitere Tests hab cih auch keine lust
EDIT:
Das ganze lief übrigens auf einem Celeron 1,2 GHz, 256 MB RAM mit MySQL 4.1 - also nicht grad das Schnellste und Neueste. Vielleicht siehts ja bei MySQL 5 anders aus.