Thank you very much for your assistance.
This issue has now been resolved, but I am going to give a bit more of context just in case someone else finds it useful.
This application is a console app, this console app was working fine on my local dev machine, however, when I deployed the app on an Azure VM, the queries to Graph API stopped working and it was giving me the error I described in my question.
So I had the suspicion this was down to configuration within the Azure portal than anything else inside the code (as the app was working correctly on the development machine using my account as Managed identity), so one of the infrastructure engineers helped me replicating the permissions of the VM to access Graph API
And after 15 minutes, it all worked well again. In summary the system managed identity of the VM had to replicate the same API permissions that my app had in order to work well on it.
Thanks again for your help and I hope this can help someone else having this issue as the error message is completely misleading!