We talked on Facebook yesterday and resolved this problem. So I’ll summarize it here in case someone needs it.
The most important thing is WordPress doesn’t support adding taxonomy to custom post type permalink by default. It seems to work only with categories and posts, but not for other custom post types/taxonomies.
And that has nothing related to how we create custom post type/taxonomy or making them hierarchical.
WooCommerce has done that with its custom code that handles rewrite rules.