This thread will focus on discussing the first problem: Users on Office365 are unable to perform Free/Busy Lookup of on-premise Exchange Users. One thread one question is easier for other users to search and reference. About the mail flow issue, I would suggest you open a new thread and let us discuss in it.
Do you mean online user cannot see the Exchange on-premises mailbox free/busy information? If so, I would suggest you have a check about the configuration of Organization Sharing on your Exchange on-premises:
Mark sure those information are correct:
Domains to share with: yourOnlineDomain.mail.onmicrosoft.com, mail.yourOnlineDomain.onmicrosoft.com, yourOnlineDomain.onmicrosoft.com (If there exist customize domain, you also need to add it)
Application URI: outlook.com
Autodiscover endpoint: https://autodiscover-s.outlook.com/autodiscover/autodiscover.svc/WSSecurity
After that, wait a while and try to check again. By the way, Exchange 2016 CU 19 is old, I would suggest you update to Exchange CU 22 and Nov21SU, it could strengthen your Exchange server security and solve some known issues.
About TLS, here is a detailed information about it: Exchange Server TLS guidance Part 2: Enabling TLS 1.2 and Identifying Clients Not Using It
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.