The second thing, which I am proposing to add at some point, is a more 'instantaneous' way for the AI to respond to losing any of its 'core' regions. So let's say Macedon, for example, starts with 8 regions. At the point where it loses two of them to anyone (except for islands, where troops are bound to get stranded), it will start spitting out armies from a few cities until it gets back to '7' of them....and they will continue spitting out those armies until they either do get back to seven, or they are defeated. This is what I did with Carthage and Seleucid in my test campaign. Both factions have less than the number of regions they should have, and both spit out free armies that have allowed them to survive the assaults on them for a long time. Now, they do have to pay the maintenance on those armies...but I even give them money if they get below a certain amount.
I like to call this a 'Hornet's Nest' AI. You may take one its cities easily, but the next and the next will get harder and harder.