Ответы очевидны.
Помечать флагом — растет база, удалять — понижение производительности (фрагментация, сама операция удаления может оказаться дорогой) и часто усложнение бизнеслогики.
Я бы не рекомендовал удалять данные из сложных баз данных, особенно если это справочники, например выставив в freign key — RESTRICT, чтобы разрешить удаление только для 'свободных' записей. Удаление записей в сложных базах данных, обычно очень сложная операция, обычно перед этим приходится проводить кучу проверок и изменений для связанных данных, поэтому флаг 'deleted' используется как упрощение или даже часть механизма для введения временной составляющей в хранение данных (база данных может являться как средством для хранения текущего состояния, так и для хранения лога изменений данных во времени)
В зависимости от задач:
1. Если удаление происходит сравнительно редко, т.е. если оверхед на размер базы незначителен — то лучше помечать флагом.
2. Если удаления и создания записей очень частые (в результате база не очень растет), то лучше удалять, плюсы от отсутствия фрагментации может оказаться недостаточным, чтобы перебить рост индексов (кстати и кэш в оперативной памяти будет зря занят).
3. Если и скорость и данные критичны, то лучше помечать флагом и удалять по крону, а чтобы минимизировать вероятность задержек на время обслуживания — разделить таблицу на кластеры (можно 'вручную' в классе работы с БД) и очищать каждый кусок отдельно, а разделение сделать с целью отделить часто используемые данные от редко используемых.