The Contacts features are once again fully operational.
We contacted MS 365 support and the problem was something on their side.
The representative stated: "Unfortunately I am unable to tell you what the cause is, if I have to guess is either something with the mailbox or the fact we deleted and re-imported the contacts. Also looking at previous cases with this issue running the diagnostics on our end fixed the problem. In your case is possible that when I completed the diagnostics it took 48 hours for the propagation to be completed. If this happens in the future again you will have to call us so that we can run diagnostics on the mailbox."