Собсно вы сами и ответили.
Единственное что приходит на ум сделать триггер который будет записывать в другую таблицу кол-во или что то такого
На двух проектах была аналогичная проблемка, там в БД по 30-40млн строк.
Решено было добавлением функции типа
Записал в БД1 - Запиши LastID в БД2
В итоге в БД2 было с десяток строк, в каждой свои LastID (нужна была разбивка по неким параметрам).
Ответ = 1мс!))))
Конечно, это если вам действительно нужно
частое получение этого вашего Count)))