Hello everyone, I do seem to have figured out the answer (at least for me).
It seems that when I am using a VPN, I get this error. I use a VPN at most times, but occasionally have to turn it off, which is why this problem disappeared from me, for seemingly no reason.
I really wish Microsoft would not 'partially' block my VPN, or at the very least add some proper error messages.
Hope this helps!