consulta mysql de uno a muchos con negación y/o múltiples criterios

Escribiría la combinación de exclusión sin subconsultas:

SELECT p.productid
FROM   products p
INNER JOIN producttags AS t ON p.productid = t.productid
LEFT OUTER JOIN producttags AS x ON p.productid = x.productid 
       AND x.tag IN ('Motorcycle', 'Green')
WHERE  p.active = 1
       AND t.tag IN ( 'Ford', 'Black', 'Skateboard' )
       AND x.productid IS NULL;

Asegúrese de tener un índice de productos sobre las dos columnas (activo, productid) en ese orden.

También debe tener un índice de etiquetas de productos sobre las dos columnas (productid, etiqueta) en ese orden.

Otra consulta que tendré que hacer es algo como todo (Coche) o (Monopatín) o (Verde Y Motocicleta) o (Rojo Y Motocicleta).

A veces, estas condiciones complejas son difíciles para el optimizador de MySQL. Una solución común es usar UNION para combinar consultas más simples:

SELECT p.productid
FROM   products p
INNER JOIN producttags AS t1 ON p.productid = t1.productid
WHERE  p.active = 1
   AND t1.tag IN ('Car', 'Skateboard')

UNION ALL

SELECT p.productid
FROM   products p
INNER JOIN producttags AS t1 ON p.productid = t1.productid
INNER JOIN producttags AS t2 ON p.productid = t2.productid 
WHERE  p.active = 1
   AND t1.tag IN ('Motorcycle')
   AND t2.tag IN ('Green', 'Red');

PD:Su tabla de etiquetado no es una tabla de Entidad-Atributo-Valor.