Are you deleting individually from the Device's manage page? Or are you doing bulk deletes from a list view? If the device's aren't getting deleted after you'd set them to be deleted, then next step should be opening a TAC case so that they can investigate if there's any locks in the database for those objects.