Если:
>Ежедневно в таблицу добавляется около 100к записей, и поэтому таблица очень большая.
и возникает проблема с 5k элементов - Ваш сайт не будет работать.

Решение проблемы:
1 - индексные поля
2 - InnoDB
3 - масштабирование базы
4 - ...