No-loss was never best option for KB players, since it doesnt offer any award for finishing game with 0 casualties. But from this way of playing did some interesting strategies come : 100% crit all range army (human+elf, or all orc depending), shrek(giant) build in CW, all dragon army, summoning galore build etc.
As you said that game needs to be made harder, it doesnt mean all enemy need to have huge army and enemy heroes to be 10+ lvl more then you. It just need to make AI better (here i`ll mention HoMM3 babies mod for theLegend).
About game being unbalanced check this
http://en.wikipedia.org/wiki/Battle_of_Gaugamela or
http://en.wikipedia.org/wiki/Battle_of_Thermopylae and talk about combats labeled as invincible.