Hi, thanks for responding. Here are answers to your questions and where I'm at now with my own problem solving.
- 365 Family
- Custom domain (legacy) hosted on outlook.com
- Personal
- Exchange
- No, I foolishly trusted the cloud recovery function.
Even though I didn't have a backup and deleted contacts had nothing in it, I did, after some digging, find deleted contacts among my deleted e-mails in the folder called "Deleted items". I restored all deleted contacts, which contained all my missing contacts but also contacts deleted a long long time ago and many duplicated so it required a whole bunch of cleaning up. Exported to .csv file using desktop Outlook and used Excel to cleanup the contacts and then imported them back into Outlook. And now it seems all good in all locations, except that desktop Outlook insisted in filing everything with "Last name", "First name" instead of the other way around even though it is set as default. Half a day wasted but at least the information is saved. 🤷
Doing the cleaning I now see contacts in the Deleted folder under contacts, as it should be, but there seems to be a bug either in the Outlook app on Android or on the server side that makes it possible to delete contacts without putting the among Deleted contacts. Sure, the original error is most likely in Android or Samsung contact management but that should not be able to overrule the backup functionality on the Outlook servers.