¿Por qué Windows no puede detectar teléfonos, incluso cuando el controlador USB está instalado?

Parece que la razón de esto es porque estás usando la versión N de Windows. Microsoft afirma explícitamente que algunas características se ven afectadas en esta versión. Los usuarios han reportado que el archivo wpdmtp.inf está faltando, y por eso hay error en el protocolo MTP.

Puedes descargar el Media Feature Pack para solucionarlo.

¿Y por qué necesita suceder esto? De ¿Qué es una edición “N” o “KN” de Windows?

Estas ediciones de Windows existen totalmente por razones legales. En 2004, la Comisión Europea encontró que Microsoft había violado la ley antimonopolio europea, abusando de su monopolio en el mercado para perjudicar a las aplicaciones de video y audio competidoras. La UE multó a Microsoft con €500 millones y requirió a Microsoft ofrecer una versión de Windows sin Windows Media Player. Los consumidores y los fabricantes de PC pueden elegir esta versión de Windows e instalar sus aplicaciones multimedia preferidas sin que Windows Media Player también esté presente. No es la única versión de Windows ofrecida en la Unión Europea, simplemente es una opción que debe estar disponible. Por eso las ediciones “N” solo están disponibles en Europa.

A menudo primero tienes que instalar el controlador y luego conectar el dispositivo. Si lo haces al revés el controlador no se aplicará correctamente. Borra la entrada MTP mostrada y desconecta + vuelve a conectar tu teléfono. Además, ejecuta Windows update con "actualizaciones para todos los productos de Microsoft" habilitado.

Con respecto a adb, tu PC nuevo es desconocido para el dispositivo (porque la clave RSA adb almacenada se ha perdido debido a la nueva instalación) y por lo tanto niega el acceso a adb (dispositivo no autorizado).
Primero debes desbloquear el dispositivo (ingresar pin/contraseña/patrón) y luego aceptar el diálogo que te pregunta si se permite que tu dispositivo se conecte a través de adb.

Y que Odin funcione al mismo tiempo es porque Odin utiliza diferentes controladores. Desde la perspectiva de tu ordenador tienes 3 dispositivos USB, uno para MTP, uno para adb y uno para Odin. Compruébalo seleccionando el dispositivo MTP y luego cambiando el "Ver" del administrador de dispositivos a "Dispositivos por conexión".

Verás todos los puntos de conexión de los dispositivos USB de tu dispositivo.