Первое что интересно, так это зачем вам это? Второе DeletionService был только в 3.0. Ну и третье: В таблице <EntityName>Base есть поле DeletionStateCode которое и отвечает за состояние записи. 2- помечено на удаление, 0 - нормальное состояние. Если у вас проблемы с ошибками от службы удаления, то вот статья на эту тему:
http://support.microsoft.com/kb/921391.