Stability of alkenes tri>di>mono, but how to explain tetra
I agree with the OP and have seen numerous examples where tetrasubstituted olefins are indeed quite difficult to make, both in the literature and in my own experience, leading to the formation of Anti-Zaitzev (Hoffman) elimination products. 
Many question writers are reluctant to make a solution where the tetra-substituted option is the correct answer. It is not as simple as the trend in carbenium ion stability where hyperconjugation and conjugation dominate around a trigonal planar (less sterically encumbered) center. 
A tetrasubstituted olefin is too sterically encumbered due to 1) two A(1,2) interactions and 2) two exo substituents (gem-dimethyl) interactions. 

Such proof for this failure in the stability trend is included in the original question as the kinetic stability of such an olefin is unusually and unexpectedly high. As far as the the thermodynamic stability, torsional strain makes effective hyperconjugation less possible in the transition state which varies only marginally upon the strength of base and the lability of the bond to the leaving group. 

This trend: mono is less stable than exo-di is less stable than cis-di is less stable than trans-di is less stable than tri is....that is about all you can correctly say about the trend. Consider why cis-disubstituted is less stable than a trans-disubstituted olefin. Now consider a tetra-substituted alkene. 

Zaitsev's "rule" like Markownikoff's "rule" is a just fast and dirty guideline for undergraduates and which both have numerous exceptions. It does not follow that tetrasubstituted must be more thermodynamically stable than tri-substituted and product ratios indicate this repeatedly in the literature. Stereoselectivity of E over Z is a non-problem compared to the difficulty of and abysmal yields when creating a tetrasubstituted olefin. 

Simply put an ellipsis ("...") after the trisubstituted alkene as that is all that can be stated to an undergraduate class without presenting a falsehood.