I've performed an experiment, in which I travelled around the city from most busy to less busy districts and the problem appeared in those more busy. I linked this to some problems with mobile network provider (carrier) and, indeed, it looks like all voice channels for 3g network are occupied. It explains different time it takes for the phone to be able to make calls (stop call-dropping).
It is some stuff the provider messed up with. Fixed by switching to another carrier.