I was frustrated by this issue until I found your comment. Excellent advice.
- Delete from site recycle bin.
- Delete from Site Collection > Site Settings > Site Collection Administration > Recycle Bin.
- Delete from End User Recycle Bin Items.
- Delete from “Deleted From End User Recycle Bin.”
That’s a lot of recycling! Once complete, I was able to delete the content type.