Greg Stolze's Reign is pretty much right up your alley here. Though its rules for "companies" (or really any organization) are written more with the assumption that the PCs jointly run a single organization, I've played in (and seen) more games that fit your description than the "standard" play. And the political side is run objectively enough that the GM can serve more as a referee for those parts.
I should also add that you get both "mass combat" rules, like for running a battle with two armies and well as a more abstracted set of rules for larger conflicts, where even the outcomes of individual battles are reduced down. So you can really choose your own level of engagement with the system.
The basic rules are in print and PDF and are fairy cheap. Reign also has its own setting, which is medieval fantasy, but it's not really "vanilla" fantasy, so you might want to start with the basic rules and build your own world around that.
Links to Reign:
Basic rules in PDF & print: http://www.rpgnow.com/product_info.php?products_id=79955
The full setting in PDF: rpgnow.com/product_info.php?products_id=59095
and in print: indiepressrevolution.com/xcart/product.php?productid=16591
A couple that would count as distant runners-up in my book are:
Savage Worlds is good for combat on the scale of a group + some allies and has mass combat rules to boot, but it lacks much in the way of rules for kingdom-building. The rules assume a lot about having maps and miniatures and things that might be trouble if you're running with straight Skype (as opposed to a virtual tabletop solution like Maptool).
5th edition D&D (and some earlier editions, though I have less direct experience with those) has mass combat rules (as of a recent free release on wizards.com) and plenty of options for stronghold-building and running an enterprise in the DMG, but that's not really its core strength and running the kind of PvP campaign you're talking about is kind of uncharted territory.