We encountered similar problems with the client. Our initial analysis was to examine the stored procedures that perform the deletion and see what restrictions were followed. When analyzing the data, we could see records that would not be displayed in the user interface, but which would prevent deletion.
We raised a ticket with SDL Tridion customer support and were able to agree with them which records should be changed in the database.
To undo this: you are not allowed to modify the database, but SDL Tridion customer support can authorize it, but only after they verify that the changes are correct and necessary. Obviously, if you try to do such things without support, you will get an unsupported system.
source share