Armok, you have a good point, however I am not sure how to go about doing that. Also I'm not entirely sure what you mean by "standard units that nothing balanced should be able to beat." Balanced meaning....?
You're doing it already! The RPS finder is such test, although it's not the purest version of it imaginable. Try this: if you remove all the restrictions on points and so on, so that the stats are completely independent and can go arbitrarily high, and then put it to run the RPS finder, there's still a fair chance it'll find one, even if it's smaller. Now if you run the finder again from scratch every time that happens sooner or later you'll always find one... but this time you did it without artificial restrictions, which means you can get more diverse and interesting outcomes!
Now this is rather slow, but it shouldn't be to hard to find plenty of corners to cut when the player wont see the simulation, and then run a single properly detailed simulation to make sure it isn't to crazily overpowered.
Here's an example of a procedure for finding the price of an unit, for a specific role:
1) int N, N=1
2) Generate 100 "generic fighter", that has hardcoded stats
3) generate (100/N rounded down) of the unit you're testing
4) have them fright
5) if the unit wins, increment N, clear the field and goto step 2
6) else (aka the generic fighters win), terminate the test, and say the units cost 10*2^N resources
Note that while units that cost the same can be quite a bit different in power, there is a fundamental limit to how overpowered they can get; the opponent can always actually build 100 of those generic fighters for the same amount of resources and take them down.
Once you grasp the concepts involved (all of this is actually base largely of evolutionary biology and economics rather than only classical game design) coming up with testing procedures like this shouldn't be to hard.