Nello standard sql è previsto il comando EXCEPT ma purtroppo Mysql non lo implementa.
Lo stratagemma è appunto quello di usare il NOT IN o un NOT EXISTS, sinceramente non so perchè non ti funziona, a occhio e croce dovrebbe essere giusta...