When Kirchhoff laws cease to be valid?
From the Wikipedia page on Kirchhoff's circuit laws:
"Both of Kirchhoff's laws can be understood as corollaries of the Maxwell equations in the low-frequency limit. They are accurate for DC circuits, and for AC circuits at frequencies where the wavelengths of electromagnetic radiation are very large compared to the circuits."

This is a first case in which they are not accurate.
From the same page, but in the Limitations section, you can find some more informations, which I will just copy here (KCL and KVL stands for Kirchhoff Current Law and Kirchhoff Voltage Law, respectively):


KCL and KVL both depend on the lumped element model being applicable to the circuit in question. When the model is not applicable, the laws do not apply.
KCL, in its usual form, is dependent on the assumption that current flows only in conductors, and that whenever current flows into one end of a conductor it immediately flows out the other end.
KVL is based on the assumption that there is no fluctuating magnetic field linking the closed loop.


On the wiki page, you can find a lot more examples regarding the cases when they are not valid. 
I also suggest you take a look at the Electrical System part on the Lumped element model page on the wiki. 
To sum it up: in most practical applications they will never "cease" to be valid. They can just become less accurate in some cases (described extensively in the wiki).