Keyn Din

По симптомам - именно кодеки. Обычно решается установкой, например, k-lite.
512М памяти - норм, для видео хватает.
ну и да, проверьте, не битое ли (конкретное) видео

Возможно, Вам стоит посмотреть в сторону PostgreSQL (по опыту - более производителен), а далее - и задуматься о переходе на NoSQL техники, если, конечно, Вам подходит неструктурированное хранилище.
А вообще смотрите по темам высоких нагрузок, горизонтального распарелливания, шардинга, ну и вообще напрягайте программистов на оптимизацию и кеширование (как известно. смена алгоритма O(n^3) на O(n log n) экономит деньги)