Обычно проблема как раз в том, чтобы восстановить стертые данные. Если задача в том, чтобы замести следы, то никаких проблем нет. Для пущей надежности можно сжать базу.

> Вопрос: Что значит "Нужно сжать базу"

Compact. Как известно, в базах данных при стирании записи не происходит автоматическое высвобождение места, а просто помечается, что данная часть файла "not in use". В результате файл по мере работы постепенно растет. Чтобы вернуть его к исходному размеру и удалить из него те участки, которые "not in use", как раз и применяется команда Compact.

В Аксессе это можно сделать: вручную из меню; специальным параметром в командной строке при вызове аппликации; программно (сжать базу, находясь при этом в другой базе). Есть также опция в свойствах базы "сжимать при выходе", но для файла с данными (а не с программой) это не подходит.

Кстати, Compact делает следующее: он создает новый файл меньшего размера, стирает старый, а потом дает новому имя старого. Так что стертым файлом тоже надо заняться - убедиться, что нельзя прочитать те секторы диска, которые он занимал.

> И если следы остаются, то как их можно обнаружить?

Обычными средствами - никак. Шпионскими - хрен их знает...

Сам факт удаления - конечно, могут отследить. Смотря что за программа и кто ее писал.