We solved the issue with MSFT and Databricks Support.

So our infrastructure was VNET injected. Technically it is possible to change the subnet size eventhough its not supported according to documentation. 

The result is then a randomized behaviour depending where Databricks puts the nodes "on the subnet". If its on the old range - all is fine and if its on the new range, you get the above mentioned behaviour.

Changing the subnet range back solved our issue.