1) Если беспокоит производительность, то удалённые записи переносить в отдельную таблицу.
2) Если объёмы таблиц не большие/не требуется высокая производительность, то делать как посоветовали выше, дополнительным флагом. В этом случае лучше сделать view, чтобы уменьшить объём рефакторинга, если захочется поменять логику (т.е. например вынести удалённые записи в отдельную таблицу или изменить способ работы с флагом удалённых записей). Сам флаг я бы делал NOT NULL и естественно добавил бы в индексы.
P.S. у меня был похожий случай, когда надо было хранить ссылки на удалённые записи, мы использовали hibernate + envers (java). Классы/поля с аннотацией @Audited порождали name_AUD таблицы, в которых хранились все те же данные, плюс два дополнительных поля — номер ревизии и тип ревизии (создание, изменение, удаление). Существовала отдельная таблица с информацией о ревизиях с полями номер ревизии, дата ревизии и дополнительные наши поля (например логин, ip-адрес). Одной транзакции соответствовала одна ревизия. Хотя, возможно этот вариант для вашей задачи слишком навороченный, привёл его просто для примера альтернативного варианта.