1. Можно завести дополнительное логическое поле в таблице, и не удалять запись, а менять значение этого поля. При необходимости добавления новой записи, сначала искать помеченную, и "затирать" ее новыми значениями (кроме счетчика, конечно). Во всех запросах к этой таблице необходимо будет применять условие по этому полю, что-бы "удаленные" записи не мешались.
2. Можно без доп. поля, присваивать полям "удаляемой" записи значение Null, если допускается.
Добавление как в п.1.
3. Можно записи удалять, а при добавлении искать "пробелы" в значениях поля-счетчика и запросом добавлять запись с указанием конкретного значения поля-счетчика.

4. Самый правильный: НЕ ИСПОЛЬЗОВАТЬ значения поля-счетчика для последовательной нумерации. Использовать самописную функцию.

5. Наверное есть исчо варианты.