Una pseudo solución que me dieron en el soporte técnico de Mi Band Master fue usar la aplicación BLE Scanner. En la primera vez que lo ejecuté encontró la Mi Band, se conectó e inmediatamente Mi Band Tools pudo conectarse y funcionar correctamente.
Desinstalé el BLE Scanner pensando que era todo y, como era de suponerse, Mi Band Tools ya no vio la pulsera. Lo instalo de nuevo y ahora BLE Scanner tampoco la veía!
Comenzaba a volverme loco ya y recordé que el Mi Fit tiene una opción que dice algo así como la Mi Band sea visible para otros. JAMAS la había cambiado, estaba como que no fuera visible para los demás. La cambio y el BLE Scanner la detectó sin problemas. Probé con la Mi Band Tools y funciona. Mi Band Master también funciona.
Queda probar qué pasa si desinstalo BLE Scanner. También probar si vuelvo a poner la pulsera como invisible a los demás (como SIEMPRE estuvo, realmente no sé por qué ahora hizo la diferencia!) si sigue funcionando...
Ya estaré actualizando la info por si le sirve a alguien más.