I just wrestled with this for over an hour. Kept getting errors like the above, or "OCID is associated with Subnet that is in use"

For me it was stuck on the Network Load Balancer and vTAP — once I manually deleted these two items the VCN deletion worked fine.