The A.I. is not very effective at coordinating its forces on the campaign map, which means that there will often be plenty of full stacks of high quality units wandering around even when you trash their main cities. However, it cannot build units without the approriate structures.

The rebellion thing is something else, though. AFAIK the troops generated are of the type that the town can naturally generate. Aparently, these rebellions have a sort of budget, and any spare cash is turned into upgrades. That's how you end up with gold-chevron troops, but you shouldn't see legionaries in a town with level 2 barracks.