I've run through all the steps in the article and removed EWS permissions and now Free/Busy between Exchange On-Premises and Exchange Online is no longer working under a certain scenario.
Working
- An Exchange On-Premises user logs in to an Exchange On-Premises mailbox - Can view Free/Busy of Exchange Online mailboxes
- An Exchange Online user logs in to an Exchange Online mailbox - Can view Free/Busy of Exchange On-Premises mailboxes
Not Working
- An Exchange Online user logs in to an Exchange On-Premises mailbox - Cannot view Free/Busy of Exchange Online mailboxes\
Update 7th September 2026: Microsoft have confirmed this is a known issue. Thank you Flare for pointing this out.
https://support.microsoft.com/en-us/servicing/exchange/server/update/2026/5127092