As the title says, what if Kings and Monarches became more aware of the order, and started demanding taxes, fees and fines paid in vis?
Edited to add: What about requirements to establishing residency in their kingdom? "Only Christian Wizards can reside in Kingdom X" similar to the certain historical laws expelling Jews/Muslims from certain areas.
I'd say that's where the Jerbiton and Tytalus with Mentem magic comes in. 
Asking for fees and fines paid in Vis seems to me like the Order would view that as a king overstepping their acceptable mandate. It also leads me to the question of “are they still merely a mundane power?” Paying taxes, sending mundane troops, those are not so bad as long as making the magi use magic in their wars isn’t part of any agreed upon agreement and there is not actually an Oath of Vassalage, which might be viewed as open ended. Some more limited oath that more proscriptive, along the lines of “I will take no part in [actions] against you, King” seem perfectly acceptable.
My first in-character question is "What is he going to do with vis?" I mean, if he can manipulate it, presumably through a magician, that magician is nosing around for recruitment into the Order.
Next: if I accept that a king can tax magi (which I might), I'd presume that mundane rulers get mundane taxes, or at least straightforward magic items "of great wonder and power" that any first-decade mage can knock out. Not vis. Possibly services and advice.
(I do accept that kings can tax, but like with faeries, they get things of value to mortals.)
As for the question in the header, some regulation, some taxation, but it's negotiable and limited.
Service is the very last thing any ruler would get as tax from the Order. Providing (magical) service on order is basically becoming a court wizard - which the Order would like very much to avoid.
If they do, I suppose they would use the vis to purchase goods and services from those who value vis, which would create good market for some Verditius, I suppose. I don't think what they want with the vis is really a controversial question.
Neither do I think there is a significant difference between taxation in vis or in silver, nor is there a significant difference between tax and rent. At the end of the day it boils down to a trade-off between the cost of the tax and the convenience of peaceful relations.
Trouble arise when the taxation borders on meddling in mundane affairs. Clearly, if one lord taxing a covenant can buy magic items far out of reach from his neighbours, we get a situation which resembles court wizardry, which is unacceptable to the Order. They would have to put their foot down, and that could mean war, and not one necessarily won, not if the nobles make a broad alliance including the church.
And once we go down this route, a lord could demand the service of a wizard just as well as that of a knight, and then the problem is more obvious.
It is a brilliant plot hook.
Paying tax or rent or scutage, providing service, otherwise accepting authority of the mundane king can be court wizardry, of course.
Failing to do so and bringing the full wrath of the King of France down on the Tribunals of Normandy and Provencal is endangering.
Now what? A widespread vanishing act? A war?
I suspect a high-level agreement, assuming one is not already in place and breached.
Magical service on order is not the only option. Responding to requests for aid, as a customary duty, is another option.
"Magus, the youngest daughter of my heir has been turned into a pig! I invoke our pact, and ask your advice and aid!"
Rather a different thing from "I require a third magic sword to slice my enemies into thin meat."
Hmm. The magus can't hold a fief, so the standard "advice and aid" owed to one's liege can't be requested.
"Thanks for your trust and the important information. I will look into it." is an adequate response even for a Quaesitor, though. Someone is clearly meddling with mundanes there, and if they are not in the Order, they perhaps might better be.
You can find an approach to high level cooperation between the HRE and the OoH in sub rosa #16 STRANGE ALLIANCES.
So in 1048 the Holy Roman Emperor, facing a threat which his privileges and armies cannot avert, turns to the Order of Hermes for help. Will magi, who still remember the consequences of corruption in the Order of Hermes, now succeed in protecting the Church from it?
An example for a more precise low level cooperation between some magi and the HRE is Triamore (see the ArM4 book from 2000).
Here is a quick overview over taxes in medieval England - since the Norman invasion a very centralized monarchy.
You find:
During the reign of King Henry III, the king and government sought consent from the nobles of England for taxes the government wished to impose. This led in 1254 to the start of the Parliament of England, when the nobles advised the king to summon knights from each shire to help advise and consent to a new tax. In the 1260s, men from the towns were included with the knights, forming the beginnings of the House of Commons of England.[15]
Taxing magi - most of them claiming very old rights to their covenants or at least having inscrutable powers - might similarly affect a monarchy: like magi getting a say in spending or use of their contributions.