One thing to remember is that certain mercs are unique to a certain region (Cilician Pirates for example) while most others are more common than rats (Barbarian Mercenaries for example) and yet others will be available in several pools, but in their home region, they will be either 1) more plentiful, or 2) gain a slight exp bonus.

Often times I end up running across a rebel general, far off in the middle of nowhere, years away from my current borders. What is somewhat fun to do is to bribe him, and hire all the mercs you find on his long journey to his new home. You just never know what that crazy boy will bring home! One time, after his trek through Scythian lands, then through Thracian holdings, past Dacian forests, through the hills of Macedonia, and then finally over the rocky alps, I ended up with an army composed of Bastarne and Thracian infantry, Sarmatian Cavalry, Scythian Horse Archers, Mercenary Hoplites, and Illyrian Mercenaries. Now THAT was a well rounded army. They went forth through the Gallic lands with sword and fire, striking the fear of the Gods into those hairy upstarts!