We've finally determined the culprit. (Update: no, I didn't!) check my other answer
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.