Custom post types and tag archive pages/permalink structure issue

/tag/thetag/ is the correct default permalink for a tag archive. There is no concept of per-post type taxonomy archives, just a single archive for all types.

The issue you have with a 404 on those pages if they only contain custom post types, is that the built in tag and category taxonomy archives by default only query the post post type. If you want to add custom types to that you need to hook pre_get_posts and add your custom types to those queries.

function wpd_custom_types_on_tag_archives( $query ){
    if( $query->is_tag() && $query->is_main_query() ){
        $query->set( 'post_type', array( 'post', 'your_custom_type' ) );
    }
}
add_action( 'pre_get_posts', 'wpd_custom_types_on_tag_archives' );