Могут быть проблемы с индексацией при использовании mysql?

mysql - это лишь способ хранения данных. С индексацией, по большому счету, никак не связано.

А от кривых урлов (cheats.php?p=3&catId=1&id=713) надо уходить, это для индексации может играет роль (разберитесь с движком, чтобы получать cheats.php/3/1/713)

Так "может" или "играет"? И сильно ли? Нужно это делать прям в ближайшее время?

Играет (может - лишнее слово :) ) Делать лучше сразу, пусть по правильному сразу индексируется (зачем дубли, если потом будете переходить?) Надеюсь, разберетесь с мод риврайт

Ответить на вопрос о возможном вреде MySQL может примерно такой запрос.

http://www.yandex.ru/yandsearch?text=Warning%3A+mysql_query%28%29&stype=www

Вероятность того, что БД будет всегда доступной, как правило тем выше, чем качественней хостинг.

динамические УРЛы (с?) от способа хранения данных не зависят. Рамблер и др. поисковики их индексируют нормально. Как тут уже посоветовали mod_rewrite Вам поможет если захотите использовать статические адреса.

Поисковики индексируют HTML, а уж как он генерится и где хранятся данные для них не имеет значения.

Урлы с большим числом параметров, как уже было говорено, лучше преобразовать к статическому виду. Вот дока на английском - http://httpd.apache.org/docs/1.3/mod/mod_rewrite.html. На русском она же - http://www.egoroff.spb.ru/portfolio/apache/mod_rewrite.html

Спасибо большое, буду разбираться!

Проблема только с Рамблером? Яндекс все хорошо кушает?

Проблема общая. В пример привел рамблер, потому что он уже поиндексил мои странички. Я уже индексил пару страниц, но выкинул их. Гугл пока полный ноль.