Consulta más eficiente que NOT IN (selección anidada)

Actualice a MySQL 5.6, que optimiza mejor las semiuniones frente a las subconsultas.

Consulte http://dev.mysql.com/doc/ refman/5.6/en/subquery-optimization.html

O bien, utilice una combinación de exclusión:

SELECT COUNT(t1.table1_id) FROM table1 t1 
LEFT OUTER JOIN table2 t2 USING (table1_id)
WHERE t2.table1_id IS NULL

Además, asegúrese de que table2.table1_id tiene un índice.