Výběr jedinečných řádků v sadě dvou možností

To je docela podobné tomu, co jste napsal, ale mělo by to být poměrně rychlé, protože NOT EXISTS je v tomto případě efektivnější než NOT IN...

mysql> select * from foo;
+----+-----+
| id | col |
+----+-----+
|  1 | Bar | 
|  1 | Foo | 
|  2 | Foo | 
|  3 | Bar | 
|  4 | Bar | 
|  4 | Foo | 
+----+-----+

SELECT id
     , col
  FROM foo f1 
 WHERE col = 'Foo' 
  OR ( col = 'Bar' AND NOT EXISTS( SELECT * 
                                     FROM foo f2
                                    WHERE f1.id  = f2.id 
                                      AND f2.col = 'Foo' 
                                 ) 
     ); 

+----+-----+
| id | col |
+----+-----+
|  1 | Foo | 
|  2 | Foo | 
|  3 | Bar | 
|  4 | Foo | 
+----+-----+