@Dimitris Yes we did manage to fix the issue but we had to create a staging slot and deploy to that slot and wait five minutes (you can set a task in devops to wait) and swap the slots.
I reached out to Azure support and this was the best solution they could give to me. The answer they gave me was that the process is actually not fully shutting down after a restart. Which is why we needed to wait 5 minutes. Hope that helps.