That just makes it more ridiculously anticlimactic when they do face it. "Seriously, that thing defeated armies? It only had 500 HP!" I've played in that game before and it was not fun.
Only if it's a solo critter. Maybe it defeated armies before by having armies of its own, and those are the forces it's spending years rebuilding.
It also doesn't have to be a straight-up battle. Look at the classic example, Lord of the Rings - nobody, even the most powerful champions, actually fights Sauron. They defeat him indirectly, largely by denying him the opportunity to fully recover his power.