Additional calendar-related features and issues within Microsoft Teams for business
Since this happens in both Teams and Outlook web/desktop, I agree this points away from a local client issue.
I’d check the user’s Teams meeting policy and Exchange mailbox next. In Teams Admin Center, verify the assigned policy has Allow scheduling for private meetings enabled. Microsoft lists this as a requirement for scheduling Teams meetings.
I’d also verify the user has a healthy Exchange Online mailbox, not just the Exchange Online license enabled. The Teams meeting integration requires an Exchange mailbox for the organizer.
If both look correct, I’d compare the affected user’s Teams/Exchange policy assignments with a working user. If the settings are identical, I'd probably open a Microsoft support case and ask them to check the Teams/Exchange provisioning state for that specific user, since the issue is reproducible across web and desktop.