Answering to my previous comment, in which I said we were experiencing similar issues with VM that had some custom network settings.
My similar issue was solved when I changed the diagnostics storage account settings. VM worked fine previously, suddenly it started acting like this. Under boot diagnostic settings it said that I had no permissions to access the diagnostic storage account. I went ahead and change settings so that everyone can access it, previously it was restricted to some of the VNets (our vpn etc.). This is weird because VM was working just fine for several weeks and problems started yesterday. No settings had been changed on any of the resources.