I know the reason why it's happening, but I'm not aware about the right solution for SharePoint Online.
When you are publishing content type, SharePoint crates a some kind of copy inside managed metadata service database. This copy is distributed around all subscribed site collections. When you update content type in the hub and click "Publish", it updates copy inside metadata service and later updated copy is distributed.
Now you deleted content type from hub, but the copy still exists in metadata service database. Even for new site collections this copy is distributed. The right way to delete content type is unpublish it first, and then delete.
To fix this issue for SharePoint on-premise there is a server side script, which unpublishes this "orphaned" content type:
$ctPublisher = New-Object Microsoft.SharePoint.Taxonomy.ContentTypeSync.ContentTypePublisher($ctsite)
...
$ctPublisher.UnPublish($contentttype)
But corresponding methods for client object model don't exist.
May be as workaround it's possible to re-create this content type with exact name and ID
, then publish, unpublish and delete.