Sounds like there was no room to write to the journal (journaling is enabled by default on HFS+). Disabling the journaling for that volume (which it doesn’t appear you tried?) will have likely allowed you to perform your deletes.
diskutil disableJournal “/Volumes/Macintosh HD” (or whatever volume is)