So after hours of trying different solutions and failing, I found fix for this among the answers here: https://github.com/Azure/AKS/issues/542

In order to fix failed state because of outdated version, I had to simply had to do the following:

Upgrade aks to version that is already there. So my version was 1.14.8 and I simply ran:

az aks upgrade --resource-group myResourceGroup --name myAKSCluster --kubernetes-version 1.14.8 

which fixed the failed state of the cluster!

After this I just ran upgrade to the correct next version (1.18.19 in my case):

az aks upgrade --resource-group myResourceGroup --name myAKSCluster --kubernetes-version 1.18.19 

I hope that this will save someone hours of frustrations :)

So after hours of trying different solutions and failing, I found fix for this among the answers here: https://github.com/Azure/AKS/issues/542

In order to fix failed state because of outdated version, I had to simply do the following:

Upgrade aks to version that is already there. So my version was 1.14.8 and I simply ran:

az aks upgrade --resource-group myResourceGroup --name myAKSCluster --kubernetes-version 1.14.8 

which fixed the failed state of the cluster!

After this I just ran upgrade to the correct next version (1.18.19 in my case):

az aks upgrade --resource-group myResourceGroup --name myAKSCluster --kubernetes-version 1.18.19 

I hope that this will save someone hours of frustrations :)