After waiting for a reply, trying out different approaches and further googleing I’d like to state that this is a pretty clear, straightforward problem. Either I’m missing out on sth. or (what I suspect but hope is not the case), WP is missing something very, very essential. Is this rather a bug (and should be filed as such)?
Custom Post Type + Custom Taxonomy should result in urls like https://www.domain.com/taxonomy/custom-post-type (or ../tag/tax-tag/custom-post). Where “taxonomy/” is not the default name I register the taxonomy with, but anything that’s put in there in the backend. Just as it’s working /w posts in different categories.
Using register_taxonomy_for_object_type I was at least able to have a category meta-box on a custom type post. I can even change the custom post’s cat. (if register_post_type _builtin is set to “true” -which it shouldn’t).
The permalink on the edit screen shown below the title is then correct. But going to that permalink gives me a 404. …->?
It seems as if much more talented developers than me have started tackling this problem after some discussion a while ago.
I’m still hoping somebody can give me a hint on how to achieve structured, pretty permalinks with custom post types. Thank you.