I would set this faction estimated difficulty as Hard or possibly very hard. It is FAR more difficult then the WRE. I won the WRE campaign the first time I played BI and I had the setting VH/VH. Conversely I have yet to win the Roxolani campaign.

Their are many reasons for the difficulty of this faction.
Starting position.
They start in one of the least valuable capitals in the game surrounded by provinces of next to no value. Using this region as a base makes it so you must wait years and years before you can even produce your Bos Infantry, the only thing you have that can stand up to the cavalry you face. This region makes no money and by the time you start to get some cash your neighbors are very big and very rich and see you as very tasty.

The territories you must gain and hold.
Only hold 10 settlements, how hard could that be? The distance between the western territory and the eastern is tremendous. You HAVE to have your capital in between them or you simply cannot hold the due to unrest. Unrest will always be a huge factor for this faction. Bigger then most others. Why? NO PEASANTS! You have to garrison your cities with herdsmen or slave spearmen and this will cost you up to 5-10 times as much per man to garrison your cities as factions that can build peasants. Good luck holding a city in Italy AND Colchis. (Not going to happen on VH/VH.)


Who you fight.
In the east you will be fighting the Sassanid empire. Hey its just the AI right? Even on VH/VH you ALWAYS slaughter the stupid AI. How tough can they be? The answer is their cavalry. If their was ever a unit that was built to cover for the mistakes of a stupid AI it was the BIG Sassanid Cavalry. They are Invulnerable to missile fire, half of them fire their OWN missiles, and they are heavy enough to take on your only real spear unit (which you cannot afford early game) head on. Yes it is the A.I. and you can defeat these armies but they hit you with a full stack EVERY OTHER TURN on VH/VH! Your main stack will be tied up fighting full stacks of sassanids as long as you are at war with them. If you are lucky then the ERE will fight the Sassanid and if you are not you will get to fight both of them at the same time.

In the west you get to fight ...... Well actually it is better to list who you will not fight in the west. The Celts and probably not the Alemani or the Franks. You will probably end up at war with everyone else at some point. ALL the hordes go past your western objective provinces at some point.

For variety the Roxolani are the most fun to be. You get to fight a huge variety of army types and often you face several different ones each turn.

The real downside is that if you are going to win you have to pull out the cheese tactics. You have to fight out all the battles on the map. You actually need to Pause like a wuss in order to win big enough to have your army able to beat the NEXT full stack. ( The A.I. can't pause so if you use pause then you are never allowed to say the A.I. sucks, try to do as well as it does without doing things it cannot do.)

Here is a summary of my 4 campaigns so far as the Roxolani.
1. Went straight west for Colchis. Took it while it was still rebel. Spent the next 100 years fighting full stacks of Sassanid around Colchis and was never able to get enough to move west. Time ran out.

2. Here I tried to move my horde at the start into the rich areas of Greece to take the fat rich cities there. Unfortunately there were other hordes that had this idea and I could not take my goal of Constantinople because the Sarmatians got there first and their horde is alot better then mine. Instead I took Thrace and Athens. The Roxolani Horde is a very weak one unfortunately and after taking 2 strong cities it is used up and does not have the strength to take another. Consant fighting in Greece weakened me and bad luck had a loyalist revolt in Athens. A full stack of gold sword, shield, and chevron Roman Heavy Infantry and Cataphracts ended any hope for me and I quit that campaign when they laid seige to my only good settlement Thrace.

3. This game I tried a new trick. I went horde right away but re occupied my city right away. This gave me lots of maintenance free troops and 2 more generals right at the start while still holding my capital. I swept the North eastern plains and began to develop my economy. After I could build Bos spears and had a very good stack I moved to Colchis and took it. Fighting the Sassanid full stacks but with a better econ then before I started to look west. In between me and my western goals were Huns, Sarmatians, WRE, ERE, and a bit of small hordes scattered about.
I started to move along the coast of the black sea to take advantage of Sea trade. Despite my best efforts the Sassanid were wearing my down bit by bit in the East but the new income from Sea trade was making up for it. That is until the ERE allied with the Sassanid and went to war with me, killing my trade at the same time as the Lombardi, who had taken out Burgundi and had most of that section of the map invaded me and sieged multiple settlements. The Sassanid broke me in the west and I went into deep debt.... fast. It was a hole I could not get out of and after many frustrating turns of things getting steadily worse it was game over.

4. My current campaign. Did the horde trick and sent my diplomats everywhere and tried to make alliances with everyone. I did not attack anything anywhere. Instead I allied with the Sassanids immediately and watched them war with the ERE. The ERE took colchis and they fought and fought to my great joy. I also allied with the huns and followed them in their rampage south west. I was able to occupy the territories they sacked and therefore expand without any real wars. I took all the slave territories and focused again on econ. I kept my armies very small and relied on diplomacy to keep me alive. It worked.
Also in this campaign I have pulled out all the stops. In the worst battles I have used pause as a tactic for the first time since I was first playing M:TW (Pause is cheating as far as I am concerned.) I have used pathing AI in sieges to lure the A.I. armies in range on my archers on the walls and decimated them and then let time run out and do it again ont he next turn. I build 7 or 8 siege towers in sieges and USE them as artillery when I assault the walls.
In this campaign I had strong armies and a decent economy. My powerful western stack pushed into Northern Greece and actually took some "real" cities while I was able to keep my trade relations with my neighbors on the Black Sea. That is until a war started with the ERE. They had lost all their non asian provinces so when they demanded that I become a protectorate I laughed and ignored them. Even though I lost some trade I had the Sarmatians and ERER rebels to trade with. I pushed towards Aquincum and took it from the Huns who held it. After that everything went to hell. The ERE made allies over the next few turns with EVERYONE that bordered me. The A.I. beat me with diplomacy. One by one each power declared war on me and invaded. Full stacks of sassanids and ERE in the east pushed up and took my capital. The Slaves appeared with his HUGE horde right on top of me and drove me out of Pannonia and Campus Campus. Burgundi invaded from the north west and the Sarmatians beat me out of the rest.

Right now I have one stack made up of almost all Untrained generals and the remains of all my armies mashed together. I am down to my original settlement and the one directly to its north.

I feel that at its heart the great weakness of the Roxolani is, ironically, its lack of peasants. With no option for any truly cheap garrison units cities will revolt constantly OR you are forced to tie up so many resources in garrisons that you cannot to take both the East AND the West.

So has anyone won as the Roxolani on VH/VH with out useing any Rome shell cheats or some personal Mod? If so please give details. :)

In my next try I am considering 4 possibilities.
1. Instead of trying to maintain a hold on cities I take with expensive garrisons I will allow the cities to revolt and then retake them and exterminate them. Cheese tactics? Yes but I have lost an awful lot.
2. Go by Boat to constantanople and take it as my capital. If I fail just restart right away.
3. Try to move to Italy for the easy pickings there and build up a huge warchest and then move back eastward.
4. Play a differenct faction just to make sure it is the faction and not me that is the cause of all this loss. Perhaps I will try the Sassanids.