I hit this error and noticed in the Azure portal that my toll-free number had a "Submit verification" link on the SMS column under Phone numbers. Seems there's a whole verification process and it can take up to 5 weeks to approve. I am trying to send SMS notifications from health checks for a single application, not do a commercial SMS campaign, so I am looking into pricing for third party SMS APIs.

From https://learn.microsoft.com/en-us/azure/communication-services/concepts/sms/sms-faq#toll-free-verification: Effective January 31, 2024, the industry’s toll-free aggregator is mandating toll-free verification and will only allow verified numbers to send SMS messages.