Non l'ho testata, ma probabilmente è la strada corretta:

Codice PHP:
SELECT idimgCOUNT(idimg) AS conteggio
FROM ib_immagini_opzioni
WHERE 
((idcriterio 2) AND (idopzione 7)) OR 
          ((
idcriterio 3) AND (idopzione 10)) OR
          ((
idcriterio 5) AND (idopzione 13))
GROUP BY idimg
HAVING conteggio 

Dove "HAVING conteggio = 3" indica che tutte e 3 le condizioni devono essere soddisfatte.