Atualize para o MySQL 5.6, que otimiza melhor as semijunções contra subconsultas.
Consulte http://dev.mysql.com/doc/ refman/5.6/en/subquery-optimization.html
Ou então use uma junção de exclusão:
SELECT COUNT(t1.table1_id) FROM table1 t1
LEFT OUTER JOIN table2 t2 USING (table1_id)
WHERE t2.table1_id IS NULL
Além disso, certifique-se de que
table2.table1_id tem um índice nele. 
