Mysql:Realización de NO EXISTE. ¿Es posible mejorar el rendimiento?

Tienes razón, puedes hacerlo mejor. Ver este artículo por Quassnoi para los detalles pero la conclusión es:

Su consulta reescrita usando NOT IN podría verse así:

SELECT *
FROM posts  
WHERE posts.id NOT IN (SELECT post_id
                       FROM comments
                       WHERE comments.comment_type = 'good'
                       AND comments.created_at BETWEEN '2010-05-01 00:00:00'
                                                   AND '2010-05-01 23:59:59')