I'm having the same issue - it started a few days (maybe a week?) ago... I've been using the outlook app on this particular phone (Samsung S23 Ultra) for over a year now (and iv'e been using Outlook other Samsung phones for even longer) and haven't had this issue before.
The signal that there was a problem was that suddenly all my contacts in WhatsApp turned into just phone numbers. Thinking that WA could have been the culprit, I uninstalled it... that had no effect on the issue (still happens when it's gone)
The one thing I've found that temporarily fixes the issue is to either clear the app data for Outlook (essentially restoring the app to defaults) or uninstall/reinstall it - the contacts will sync correctly for a few hours but will eventually get borked again.
Resetting the account from within the Outlook app has no effect, nor does clearing the app cache, or disabling/re-enabling sync, or deleting the account and adding it back.
Copliot suggested setting the battery usage to unrestricted for Outlook - this had no effect.