Selección de filas únicas en un conjunto de dos posibilidades

Esto es bastante similar a lo que escribiste, pero debería ser bastante rápido ya que NOT EXISTS es más eficiente, en este caso, que 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 | 
+----+-----+