In order to change the bundle ID of an app in App Store Connect, there cannot be any previously-uploaded builds; if there are, the bundle ID cannot be edited. Therefore, to change the bundle ID (and subsequently remove an app's build history from App Store Connect), would one have to remove the app from App Store Connect and reclaim it? When an app is removed this way, the app's name is released to other developers, but is that immediate? And would anything prevent me from creating a new app with the same name right after I removed it from App Store Connect? The app is still in the prepare-for-submission phase.
I've gone through this process to hand an app over to another developer - we didn't care about losing the build history, so this is faster than transferring it.
would one have to remove the app from App Store Connect and reclaim it?
I believe that is the case, although you probably could rename the original rather than deleting it.
When an app is removed this way, the app's name is released to other developers, but is that immediate? And would anything prevent me from creating a new app with the same name right after I removed it from App Store Connect?
In my case, the other developer was able to use the name within an hour. Nothing should prevent you from re-using the name, as long as no other developer grabs it before you do.
In your case, I would try to register the name with the new bundle ID right away, and just re-try ever couple of minutes until you get it back. I wouldn't be surprised if it takes a little time to get all of Apple's systems updated.
Please let us know the result!