The not so obvious solution here was to actually not use SwiftUI. To get the UIKit behaviour I wrapped a UIKit UITabBarController in a SwiftUI UIViewControllerRepresentable like in this example: https://developer.apple.com/tutorials/swiftui/interfacing-with-uikit.
I show a basic implementation here. The full up to date implementation is on github: https://gist.github.com/Amzd/2eb5b941865e8c5cccf149e6e07c8810 
Wrap the UIKit UITabBarController in a SwiftUI view:
struct UIKitTabView: View {
    var viewControllers: [UIHostingController<AnyView>]
    init(_ tabs: [Tab]) {
        self.viewControllers = tabs.map {
            let host = UIHostingController(rootView: $0.view)
            host.tabBarItem = $0.barItem
            return host
        }
    }
    var body: some View {
        TabBarController(controllers: viewControllers)
            .edgesIgnoringSafeArea(.all)
    }
    struct Tab {
        var view: AnyView
        var barItem: UITabBarItem
        init<V: View>(view: V, barItem: UITabBarItem) {
            self.view = AnyView(view)
            self.barItem = barItem
        }
    }
}
struct TabBarController: UIViewControllerRepresentable {
    var controllers: [UIViewController]
    func makeUIViewController(context: Context) -> UITabBarController {
        let tabBarController = UITabBarController()
        tabBarController.viewControllers = controllers
        return tabBarController
    }
    func updateUIViewController(_ uiViewController: UITabBarController, context: Context) {
    }
}
Example usage:
struct ExampleView: View {
    @State var text: String = ""
    var body: some View {
        UIKitTabView([
            UIKitTabView.Tab(
                view: NavView(), 
                barItem: UITabBarItem(title: "First", image: nil, selectedImage: nil)
            ),
            UIKitTabView.Tab(
                view: Text("Second View"), 
                barItem: UITabBarItem(title: "Second", image: nil, selectedImage: nil)
            )
        ])
    }
}
struct NavView: View {
    var body: some View {
        NavigationView {
            VStack {
                NavigationLink(destination: Text("This page stays when you switch back and forth between tabs (as expected on iOS)")) {
                    Text("Go to detail")
                }
            }
        }
    }
}