I start the animation using Alt+A shortcut and in 80% of times cloth keeps hanging in the air, doesn't fall or interact with objects. And if I try to move it couple times in a row and slightly change collision, it starts working correctly and leads to a simulation. What could be causing the problem?
That sounds strange! If it keeps happening, I would recommend reporting it to https://developer.blender.org/