User keeps getting asked to MFA, even though "remember device" is selected

Hi,

We have one user (latest iOS version, 15.6.1) that is being asked to MFA almost on every login (but not always).
Our MFA policy is “always”. We’ve enabled Adaptive MFA Risk Assessment, and do not understand why is he getting “no_device_history”:

riskAssessment": {
“confidence”: “high”,
“version”: “1”,
“assessments”: {
“UntrustedIP”: {
“confidence”: “high”,
“code”: “not_found_on_deny_list”
},
“NewDevice”: {
“confidence”: “low”,
“code”: “no_device_history”
},
“ImpossibleTravel”: {
“confidence”: “high”,
“code”: “location_history_not_found”
}
}
}

Any advice or debug suggestions (from remote, we do not have access to the user/device) will be appreciated.

Thanks,
Assaf