Hi @DANIEL DIGREGORIO,
Thanks for sharing the details. Based on the Event ID 5016 ("could not discover the route to the connector") and the CU upgrade from 15.2.1118.7 to 15.2.1748.10, it's very likely that one or both servers are still in maintenance mode, which would prevent routing connectors from functioning properly.
Great callout by @Hien-L regarding maintenance mode. To take your Exchange server out of maintenance, try the following steps given in article-
https://community.spiceworks.com/t/how-to-take-exchange-server-out-of-maintenance-mode/1014433