could indeed be the desert environment giving bonus on "desert warfare"... and mali on management etc. Normally however I only send particulary warlike Generals(FMs) followed by client rulers to arabia. meaning I don't care much about the management skills of the generals and the Client rulers don't see much battle, which explains why I did not encounter this.

i get plenty of heroic victories in Greece but for some reason when I fight the Saba, my generals just get a billion stars.
sure, however I assume you get more and better heroic victories in arabia. Not that you would consider them heroic but the engine does not really take the frailness of sabaic forces into account.