No sé por qué de repente funciona más lentamente, pero recomiendo convertirlo a una combinación, que debería funcionar mejor:
SELECT t.*
FROM temp_company t
LEFT JOIN company c ON c.number = t.number
WHERE c.number is null
Esta es una forma bastante estándar de abordar un not in (...) a través de una unión, y funciona porque las uniones externas que no la coincidencia tiene valores nulos en las columnas de la tabla unida.
