I'd also suggest making your own critter. Okay, you can take something like the Rakshasa as a baseline, but remove the ultra-specific stuff (Maze and blessed crossbow bolts?), change the physical appearance to be more human-like, and add a few nifty things of your own. But frankly, while that method works great for one-shot enemies, it's not so good for recurring types. Sooner or later the players might figure out what it was based on. Even if it's not that obvious, the players will be using the same tactics they've always used.
I'd reinforce an earlier suggestion: why exactly was this race powerful enough to gain control? Everyone's used to the psionic race that reads thoughts and dominates minds. What if it was simpler than that?
Make a lawful evil ECL+1 race that has minor stat boosts (STR +2, CON +2, INT +2, CHA -2), DR 5/chaotic, Fast Healing 1, and some severe drawbacks, including light vulnerabilities and double damage from sonic attacks. As an additional benefit, give them better "technology"; for example, maybe all of their weapons are automatically Keen.
The armies of this race would be practically unstoppable against the standard conscript armies of the world. Even though the benefits aren't that impressive, there'd be this whole mythos of immortality about them, where fallen soldiers immediately got back up to continue fighting, and their weapons cut right through the best human armor. With no real need for healing, their attacks never pause or break; even if you kill a few, attrition will eventually overwhelm you. Sure, everyone might know their vulnerabilities, but where are you going to find enough chaotic weapons or sonic attacks to equip an entire army?
Then, of course, they're led by a smart Evil Overlord type who's actually read the Top 100 Things I'd Do list a few times. Someone who actually plans ahead and knows how to train a large army to be more than cannon fodder.
Anyway, you don't need to stack up tons of special abilities to make a good enemy; class levels work just fine for that. Just give a few basic abilities that'd make them invulnerable to peasant soldiers, and you're set.
