Issue: Unable to acquire access token via NAA flow in Outlook Addin

I have an Outlook addin, which uses the NAA flow as shown in this template: https://github.com/OfficeDev/Office-Add-in-samples/tree/main/Samples/auth/Outlook-Event-SSO-NAA

I use it in 2 different Azure App Registrations, meaning I have a development environment and a pre-production environment.
The application code is the same, the only difference is the defined Client ID points to the respective App Registration.
My addin can acquire an access token via the PublicClientApplication instance without problems in my development environment. However, it is not possible to acquire it in my pre-production environment.

I receive an error message stating there is an incorrect configuration. It points to an issue between the Broker app and MS Graph: "AADSTS65002: Consent between first party application '5d661950-3475-41cd-a2c3-d671a3162bc1' and first party resource '00000003-0000-0000-c000-000000000000' must be configured via preauthorization - applications owned and operated by Microsoft must get approval from the API owner before requesting tokens for that API."

This makes no sense to me, because I have granted all the API Permissions I need, and my App Registrations are completely similar in every regard.
My redirect uri is using the broker mulithub: "brk-multi://<app-domain>

What am I supposed to do to solve this?

I am attaching the full error message below, but with the redacted client id:
Unable to acquire token interactively: ServerError: native_auth_error: IncorrectConfiguration {"Description":"(pii)","Domain":"com.microsoft.oneauth","ErrorCode":"2002","Message":"Access denied for the resource.","SystemErrorCode":"3399614466","Tag":"7q6cl","Type":"OneAuth","additional_query_parameters_count":"1","all_error_tags":"7q6cl","api_error_code":"3399614466","api_error_context":"(pii)","api_error_tag":"7q6cl","api_name":"AcquireTokenInteractively","api_status_code":"StatusInternal::IncorrectConfiguration","auth_flow":"Broker","authority_type":"AAD","authorization_type":"Interactive","broker_app_used":"true","client_id":"5d661950-3475-41cd-a2c3-d671a3162bc1","correlation_id":"0195947a-32b5-7d5c-9313-3dee806329f4","is_successful":"false","msal_version":"1.1.0+8d124870","nested_client_id":"<redacted>","normalized_realm":"fca7a86c-308d-4875-8485-3654af8f06f9","original_authority":"https://login.microsoft.com/common","request_duration":"1876","request_eligible_for_broker":"true","start_time":"2025-03-14T11:46:33.000Z","stop_time":"2025-03-14T11:46:35.000Z","storage_read":"DAMD","ui_event_count":"1","wam_telemetry":"{"x_ms_clitelem":"1,65002,0,,","ui_visible":false,"server_error_code":65002,"scope":"User.Read Sites.Selected offline_access openid profile","redirect_uri":"ms-appx-web://Microsoft.AAD.BrokerPlugin/5d661950-3475-41cd-a2c3-d671a3162bc1","provider_id":"https://login.windows.net","oauth_error_code":"invalid_request","http_status":400,"http_event_count":8,"http_content_type":"application/json; charset=utf-8","http_content_size":753,"device_join":"haadj","correlation_id":"{0195947a-32b5-7d5c-9313-3dee806329f4}","client_id":"5d661950-3475-41cd-a2c3-d671a3162bc1","cache_event_count":0,"broker_version":"10.0.22621.4830","authority":"https://login.microsoftonline.com/<redacted>","api_error_code":-895352830,"account_join_on_start":"primary","account_join_on_end":"primary","silent_code":3399614466,"silent_bi_sub_code":0,"silent_message":"V2Error: invalid_request AADSTS65002: Consent between first party application '5d661950-3475-41cd-a2c3-d671a3162bc1' and first party resource '00000003-0000-0000-c000-000000000000' must be configured via preauthorization - applications owned and operated by Microsoft must get approval from the API owner before requesting tokens for that API. Trace ID: 2950945b-d655-4f43-9398-20dba41f5c00 Correlation ID: 0195947a-32b5-7d5c-9313-3dee806329f4 Timestamp: 2025-03-14 11:46:35Z","silent_mats":{"x_ms_clitelem":"1,65002,0,,","ui_visible":false,"server_error_code":65002,"scope":"User.Read Sites.Selected offline_access openid profile","redirect_uri":"ms-appx-web://Microsoft.AAD.BrokerPlugin/5d661950-3475-41cd-a2c3-d671a3162bc1","provider_id":"https://login.windows.net","oauth_error_code":"invalid_request","http_status":400,"http_event_count":8,"http_content_type":"application/json; charset=utf-8","http_content_size":753,"device_join":"haadj","correlation_id":"{0195947a-32b5-7d5c-9313-3dee806329f4}","client_id":"5d661950-3475-41cd-a2c3-d671a3162bc1","cache_event_count":0,"broker_version":"10.0.22621.4830","authority":"https://login.microsoftonline.com/<redacted>","api_error_code":-895352830,"account_join_on_start":"primary","account_join_on_end":"primary"},"silent_status":5,"is_cached":0}","was_request_throttled":"false"}