Some users cannot authenticate with SSO. api/usertoken/GetToken returns 404

[brnowakowski]

Version

SDK Platform: C#
SDK Version: Bot Builder 4.18.0
Active Channels: Teams
Deployment Environment: Azure Bot Service

Describe the bug

Some users cannot authenticate in our Bot using SSO. Logs indicate that endpoint https://api.botframework.com/api/usertoken/GetToken?userId={user-id}&connectionName=BotOAuth&channelId=msteams returns 404.
This issue affects only some of users, for some it works fine.
SSO worked fine for users with this problem before, no code or configuration changes were made in bot.

GetToken does not work for every user if we create new Connection (with exactly the same setting as existing connection) in Azure Bot resource.

Expected behavior

Successful response with token or error with clear message if something is wrong

Additional context

We based our bot on sample Bot SSO Setup

        public MainDialog(IConfiguration configuration, ILogger<MainDialog> logger)
            : base(nameof(MainDialog), configuration["ConnectionName"])
        {
            _logger = logger;

            AddDialog(new OAuthPrompt(
                nameof(OAuthPrompt),
                new OAuthPromptSettings
                {
                    ConnectionName = ConnectionName,
                    Text = "Please Sign In",
                    Title = "Sign In",
                    Timeout = 300000, // User has 5 minutes to login (1000 * 60 * 5)
                    EndOnInvalidMessage = true
                }));

            AddDialog(new ConfirmPrompt(nameof(ConfirmPrompt)));

            AddDialog(new WaterfallDialog(nameof(WaterfallDialog), new WaterfallStep[]
            {
                PromptStepAsync,
                LoginStepAsync,
                DisplayTokenPhase1Async,
                DisplayTokenPhase2Async,
            }));

            // The initial child Dialog to run.
            InitialDialogId = nameof(WaterfallDialog);
        }

        private async Task<DialogTurnResult> PromptStepAsync(WaterfallStepContext stepContext, CancellationToken cancellationToken)
        {
            _logger.LogInformation("PromptStepAsync() called.");
            return await stepContext.BeginDialogAsync(nameof(OAuthPrompt), null, cancellationToken);
        }

        private async Task<DialogTurnResult> LoginStepAsync(WaterfallStepContext stepContext, CancellationToken cancellationToken)
        {
            // Get the token from the previous step. Note that we could also have gotten the
            // token directly from the prompt itself. There is an example of this in the next method.
            var tokenResponse = (TokenResponse)stepContext.Result;
            // Some users does not get token
            if (tokenResponse?.Token != null)
            {
                ...
            }
        }

[tracyboehrer]

Have you posted this issue to the Teams Samples repo?