Ноги у флага deleted растут из древних-древних времен, когда "базой данных" обзывали разрозненное скопище файлов почти регулярной структуры, а хранились эти файлы на дискетах и каждое действие с этой "базой данных" стоило ресурсов и временных и механических в виде износа головок/дискеты )
На сегодняшний день ядра распространенных СУБД позволяют выстраивать полноценные схемы БД, указывая связи между таблицами (constrains, references, cascades и т.п.)
И в общем-то принципиальных противопоказаний для реального удаления, а не пометки записей - нет.
При желании/хотении истории операций - можно сливать удаленные записи в отдельную таблицу истории (возможно трансформировав и порезав не имеющие актуальности данные).