We've finally determined the culprit.
It happens when we run the following command:
PSConfig.exe -cmd upgrade -inplace b2b -force -cmd applicationcontent -install -cmd installfeatures
When the upgrade process fails at about 10% - this annoying verbose problem appears.
We've checked it on 2 "healthy" farms and managed to replicated this problem.