The item you are trying to delete, Does it have any CAD dataset that is used in assembly? If yes, then you have to remove it from CAD assembly also. Removing item only from structure in Teamcenter will not work.
Testing: NX 11 | NX 12 | TCIN
TC 11.2 | TC Vis 11.3 | AWC 3.2
It had the 3d model dataset used in assemblies, but I removed it from the assemblies. I think that the problem is that TC stores old versions (not revisions) of the assemblies and in the old versions, the dataset of the part is still used.