Вам не нужно возвращать данные из вложенных подзапросов. Я не уверен, что это повлияет на индексирование, но его легче читать.
И EXISTS / JOIN, вероятно, лучше IMHO, чем при использовании IN
SELECT *
FROM
A
JOIN
(SELECT LEFT(B,5) AS b1
FROM A
GROUP BY LEFT(B,5)
HAVING COUNT(DISTINCT C) = 1
) t1 On LEFT(A.B, 5) = t1.b1
JOIN
(SELECT C AS C1
FROM A
GROUP BY C
HAVING COUNT(DISTINCT LEFT(B,5)) = 1
) t2 ON A.C = t2.c1
Но вам понадобится вычисляемый столбец, как сказал marc_s, по крайней мере,
И 2 индекса: один на (computed, C)
и другой на (C, computed)