AngryGM Says Something About This
Once your characters are obviously going to win, end the encounter/fight. That's tough, but I'm going to sum up what he said. (You should still read it, though) You need to figure out what the main question the encounter is trying to answer, and when the answer becomes obvious, end the encounter! Yes, I know AngryDM's advice talks about encounters in 4e, but you can apply this idea to 3.5e.
Flying Creatures
Open areas favor those who are mobile. Flying is a super easy way to be mobile. Use creatures with fly speeds! Is this a "hard counter" to your players? It can be seen that way. Especially if you have loads of them, because the increased mobility of flying creatures can make the PCs the slow ones!
Fight Fire With Fire!
Certainly, playing like a Mongol horse archer isn't something unique to your players. Other people would be smart like your PCs and would specialize in this tactic. This has the potential to make encounters sprawling things, covering very large distances, but that does happen.
Tower Shields, Terrain, and Spells
Grant cover from ranged attacks! Yay! A few people together could effectively block those archers. Terrain can grant cover, too, even in flat areas. Consider the great plains of the US. They are "flat," but not flat enough that a horse can run directly from any point to any other point. There ought to be variations and things to hide behind. Additionally the flat(er) terrain can give someone on top of a modest hill the chance to spot the PCs coming.
What about clouds of fog? Firewalls? Those are all things that can shut down this fighting style. If your villains know the party, and truly wish them harm, they will employ tactics and set up ambushes where the party will lose their mobility. Palisades and ditches can be used in place of magic.
Consider the Hard Target
Additionally, this hit-and-run style is really bad against "hard targets" like castles, forts, and other entrenched positions. Sure, you can scare the defenders inside, but you need more than arrows to break it. These could very easily require the PCs to (gasp) dismount!
Your Difficulty Calculation is Incorrect
The XP numbers represent the lower end of each type, such that:
Your encounter was therefore hard, not deadly.
Difficulty Comes in Depth
Any single encounter, unless ridiculously deadly, will not challenge a party if they are allowed to have a long rest between every encounter. Difficulty comes when many encounters slowly whittle down the party's resources.
Further Reading
On the topic of creating and running challenging combat encounters, you may wish to read the following articles by the Angry GM (bad language warning):
Best Answer
Very roughly, although this is certainly not true for all levels (see Kobold Fight Club), a creature is a medium challenge for four PCs of the same level as its CR. For example, a CR 3 creature is a medium challenge for 4 level 3 PCs. By this metric, a player should be worth about 1/4 of a monster with a CR of their level. We could therefore say that a character's CR is 1/4 of their level.
However, this assumes that the characters are conserving resources in each encounter, as they have several encounters within the 'adventuring day' (pg. 84 DMG). CRs are not balanced for a party that blows every spell slot in one encounter - even supposedly 'deadly' encounters become trivial if that happens.
So, if you play the duplicate characters appropriately (i.e. as if they were conserving resources), then you could reasonably put their CR at 1/4 of their level. To do this, you would just need to use cantrips for the spellcasters, with maybe the occasional spell (depending on their level), and avoid using class features like maneuvers every turn. Essentially, play the duplicates as your players normally play their characters.
However, if you want to play the duplicates to their full potential, chain casting fireballs and the like, then a different approach will be needed. As other answers have suggested, you will need to use the CR rules in the DMG (pg. 274). As an experiment, I decided to calculate the CR of my party of 6 level 6 characters. I assumed that the characters used their most powerful ability for each of the three turns that the damage is averaged over (see pg. 277 DMG for explanation).
Sorcerer:
Fighter
Paladin
Wizard
Bard
Druid
Summary
I have no idea why this turned up such a range of CRs - perhaps that is the topic of another question. I am almost certain that my calculations are correct. My suspicion is that it is partly due to my group's optimisation, and partly due to some classes having more utility and less simple damage in combat.
What is the Difficulty?
Choosing creatures of equal CR to the ones calculated above in Kobold Fight Club turns up:
It's worth noting that 3 CR 1 monsters, and 3 CR 2 monsters (which is equivalent to saying that a character's CR is 1/4 of their level) turns up a 2,950 Adjusted XP, easy fight. That just shows what a difference using each character's most powerful abilities every turn makes.
A Conclusion
I have no idea how this changes across levels, and have no doubt that it will be different for every group, depending on how well optimised for combat the characters are. Nevertheless, it is clear that the encounter will be deadly. Proceed with caution.
It's also worth noting that character's defensive CRs are usually very low (the fighter was an exception, with 20 AC - an AC that isn't even on the CR list). This means that their HP and AC are, on average, much lower than a monster of the equivalent CR. As a result, the encounter should be quick and brutal, with both your characters and the duplicates dropping very fast.