@Nilrim: What stage in the game is this? In the industrial age and later is perfectly possible to have this level of military and be the most advanced with only 4 or 5 cities (and I've done it myself more than once). Unit upkeep for 50 to 60 units is at most 50 to 60 gpt, and probably much less, not at all improbable once a civ is up and running. The number of cities involved is far less important in Civ 4, and it's not uncommon for the capital to give production and commerce equal to most of the rest of my empire put together. As for replacing half the army during wartime, a civ that has focused on four cities ought to be able to built a unit almost every turn in each of them, to say nothing of drafting, pop-rushing and buying units as well. There is nothing here that would remotely surprise me if I saw it in a multiplayer game, so I see no reason to assume the AI is cheating because it isn't being incompetant.
The AI has substantial bonuses to upkeep at the higher difficulty levels, but these are no more "cheating" than the bonuses it receives to research and production at levels above noble.