Записи удаляются из базы не сразу после нажатия кнопки удаления, а специальным процессом, по мере высвобождения ресурсов системы. Но это для справки. Обычно ссылки на такие записи ведут на системную страницу "запись не найдена". Я думаю вам следует включить логи и посмотреть не говорит ли что-нибудь система на тему блокировки удаляемых записей: в 3.0 была проблема когда для некоторых связей каскадные операции вступали в конфликт с защитой целостности данных:
http://support.microsoft.com/kb/921391