hexen

ALTER TABLE `table` ADD INDEX ( ` A`).
ALTER TABLE `table` ADD INDEX ( ` A,B,C`)
ALTER TABLE `table` ADD INDEX ( ` A,C,D`).
ALTER TABLE `table` ADD INDEX ( `B,C`)
Это правильно, если данных много.
Можно добавлять индексы не сразу, а по мере того, как будешь замечать, что соответствующий запрос тормозит.
Может быть вообще эти индексы не надо будет добавлять.

Я настойчиво советую использовать лучше postgresql для такой задачи. Ну просто лучше он работает, чем mysql.
У каждого из твоих подходов свои плюсы и минусы.

Если одна база:
+
Удобно оперировать одной базой
Удобно накатывать скрипты обновления на одну базу
Удобно администрировать одну базу

— база разрастается сильно, если много клиентов (существенный минус)
Таблицы разрастаются быстродействие снижается

Если много баз
+
база не разрастается сильно
Таблицы не разрастаются

— Не удобно оперировать несколькими базами базой
Не удобно накатывать скрипты обновления на много баз
Не удобно администрировать много баз, усложняются административные интерфейсы

Я бы пошел следующим путем:
Если много данных в среднем от клиента, то под каждого клиента отдельная база.
Если не много данных в среднем от клиента, а клиентов много, то делал бы в одной базе.