Hi @Aleksey Kucherovskiy Syrve,
Thank you for posting to Microsoft Community.
Based on your description, I understand you got an issue when trying to share calendar between different Office 365 tenants and you see the Autodiscover error in logging.
And I want to confirm if you mean the user in one client can see the free/busy but the user in another client cannot.
However, you could try the following to troubleshooting. Please kindly double check your organization relationship setup and sharing policies to ensure they are correctly configured.
Run the Get-FederationInformation -DomainName yourdomain.com command to verify the federation configuration.
Checking DNS records (especially the CNAME record for Autodiscover) to make sure they are pointing correctly.
Use Test-OutlookWebServices -Identity user@yourdomain.com command to validate the Autodiscover service configuration.
Since you're already using the Remote Connectivity Analyzer, please check the detailed results to identify where the redirections are occurring.
Also please consider if it is external client issue by trying other client for the user since I have test creating organization relationship to share free/busy with other tenant without issue.
Hope it helps.