It's not quite as simple as destroying AI units, though that's certainly an important part of the answer. Because the "too many units" check is performed when attempting to create a unit, and unit creation happens at the beginning of your turn, every AI civ's production will be processed before you get a chance to replace the destroyed units. If you're in a situation with more than one large enemy civ, any losses you take could be replaced by fresh enemies with no chance to build reinforcements.
Can you provoke war between AI civs? Turns are always processed in order by color, so if you can get the two civs before you to fight, their destroyed units are your opportunity to grow. If you're looking to replace your own outdated troops, stack them next to one of the last civ's cities and let them be destroyed. If you can only make room for a few units this way, consider spies, gear your cities to produce gold, and reduce enemy production capability by bribing cities.
Can you post a save from the game in question? It sounds like a fun problem to get hands-on with.