Простите, но у меня MySQL с PHP нормально себя чувствовали и на 100Гб базе. Грамотно проставленные индексы, оптимизированные запросы, разумная структура таблиц и все нормально работает.
В проекте используется PrototypeJS версии 1.6.0.2. В этой версии, если использовать CSS селектор, эта проблема проявляется все равно. В более свежих версиях это пофикшено, но обновлять опасаюсь, нужно будет всесторонне тестировать, на тему «а не поломалось ли что». А проблему желательно устранить побыстрее.