mark_ablov

INSERT INTO… + SUBSTR()?

1.
Не понимаю на чём вы планируете выйграть во втором случае.
Индексов больше, внутренних запросов больше, кэширование хуже, и так далее.
Если уж и задумываться об оптимизации гигантских таблиц, то существует партиционирование.

Смотря что вам с этими ID'ами дальше делать.
Если хотите JOIN'ить, то лучше сделать промежуточную таблицу как все делают для many-to-many иерарихй.

2 вариант имхо лучший.
Дабы избежать коллизий того типа о котором вы упомянули достаточно хранить только измененное поле/поля в одной записи в таблице ревизий, а остальные — NULL.

Sphinx / Solr

Главное убедиться что конфиги совпадают относительно пары ключевых моментов.
В прицнипе, если что mysql довольно внятно ругнётся.

Декомпрессия в фоне?
Или если не нужна совместимость с IE/Opera, то можно вполне и Byte Arrays использовать, что ускорит неимоверно, и позволит отказаться от фона.

MySQL + MyISAM вполне потянут.

проксирование запросов?

Если хочется php — phpdaemon
А вообще node.js хорошее решение.

зависит от размера БД, конечно.
Если база велика я бы комбинировал флаг + удаление по крону + OPTIMIZE во время простоя ночью.