Based on your description, this phenomenon occurs sometimes, sometimes not. I think the configuration in your organization is correct, this phenomenon may related with network. It is suggested migrated mailboxes to Exchange online, Free/Busy will work better in the same side.
About this phenomenon, you could try to remove this exist permission, then give a higher level of permission, then check whether it could works better. You can also create a “Individual Sharing” in EAC under Organization. Then apply this new sharing policy to the mailbox that you want to shared calendar.
How long does it take for permissions to go into effect or to be removed?
For Exchange on-premises, it could works quickly. For Exchange online, there may exist some delay. At least they should take effect within 24 hours.
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.