Searches of Early English Books Online find 77 matches in 57 records for exhorbitant during the period from 1500–1700 and 5,324 matches in 3,047 records for exorbitant during the same period. So even though the variant spelling exhorbitant is not hard to find during this period, it is much less common than the spelling that we accept as correct today.
The most striking thing about these matches is the extent to which the earliest ones are concentrated in Scotland: the seven oldest publications, ranging from 1538 to 1575, are Scottish—and some of the government decrees cited in one of these sources date to as early as 1488.
The earliest EEBO match for exhorbitant comes from David Lindsay, The Complaynte and Testament of a Popiniay Which Lyeth Sore Wounded and Maye Not Dye, Tyll Euery Man Hathe Herd What He Sayth: Wherfore Gentyll Readers Haste You yt he Were Oute of His Payne (1538):
Kynge Iames the fyrst, patrone of prudence / Gem of angyne, and perle of polecy / Well of iustyce, and floode of eloquence / Whose vertue doth transcende my fantasy / For to discryue yet when he stode most hye / By false exhorbitant conspyracyoun / That prudent prynce was pituously put doun
Lindsay, who is Scottish, is writing here about James I of Scotland. The next-earliest instance of exhorbitant is likewise from a book of Scottish authorship. From Hector Boece, Heir Beginnis the Hystory and Croniklis of Scotland (1540[?}):
Conarus beand degradit in yis maner ye nobillis chesit Argadus capitane of A[rg]yle to be gouernour of ye realme sa lan• as Conarus wes in presoun. This Argadus in ye begynnyng of his auctorite tuke gret laubour for ornament of commoun weill. And stanchit thift, reif, & slauchter, and all othir sic exhorbitant crimes with meruellus craft and prudence.
Boece died in 1536, so this instance is probably even older than the one by Lindsay. Lindsay is also the author of the third-earliest instance. From David Lindsay, Ane Dialog Betuix Experience and Ane Courteour off the Miserabyll Estait of the Warld (1554):
Ouer the warld, mony one hundreth ʒeir / Bot gentyll Iulyus, allace / Rang Empriour, bot lytill space / Quhilk I thynk petye tyll deplore / In fyue Moneth and lytill more / By fals exhorbitant treasoun / That prudent Prince, wes trampit doun / And murdrest in his counsall hous / By creuell Brutus, and Cascius
Ʒe Lordis, and Barronis, more and les / That ʒour pure Tennantis dois oppres / Be gret Gyrsome, and dowbyll maill / More than ʒour landis bene auaill / With sore exhorbitant cariage / With merchetis of thare mariage / Tormentit boith in peace and weir / With birdyngis more than thay may beir
From next oldest text containing exhorbitant is The Actis and Constitutiounis of the Realme of Scotland Maid in Parliamentis Haldin Be the Rycht Excellent, Hie and Mychtie Princeis Kingis James the First, Secund, Thrid, Feird, Fyft, and in Tyme of Marie now Quene of Scottis, , Viseit, Correctid, and Extractit furth of the Registers by the Lordis Depute be Hir Maiestieis Speciall Commissioun Thairto (1566), which uses the spelling twelve times, starting with this instance from a parliamentary decree issued in 1488 during the reign of James IV:
It is statute and ordanit for the weill and honour of our Souerane Lord, the commoun gude, and proffite vniuersall of his Realme and liegis, and for the eschewing of innumerabill skaith and dampnage, that his hienes, Realme, and liegis daylie incurris, and sustenis throw the exhorbitant coistis and expensis daylie done be Kirkmen vpone the impetratioun and purchessing, at the court of Rome beneficis electiue, and diuers vthers, that mycht be geuin and prouydit within the Realme, contrare the actis of Parliament maid thairupone, and contrare diuers faculteis and priuilegis, that our Souerane Lord and his progenitouris of gude mynde hes had, and hes of the Kirk of Rome, and als in purchessing and inbringing of nouelteis and innouatiounis in the Kirk without the auisement of our Souerane Lord in vtter heirschip and destituting of the Realme of all money, and putting of our Souerane Lord and diuers vthers patronis fra thair possessioun and vse of thair saidis faculteis, priuilegeis, and rychtis of dispositioun of beneficis:
If the decree was published in English in 1488, this would be the oldest instance of exhorbitant, although a second decree, later in 1488, also uses the spelling. Others follow in 1515 (four instances), 1542 (five instances), 1563, and 1566.
From a Scottish edition of Aesop, The Morall fabillis of Esope the Phrygian, Compylit in Eloquent, and Ornate Scottis Meter, be Maister Robert Henrisone, Scholemaister of Dunfermeling (1570):
He wraithit me, and than I culd him warne, / Within ane ʒeir, and I brukit my heid, / I suld be wrokkin on him, or on his barne, / For his exhorbitant and frawart pleid. / Thow •all doutles for his deidis be deid. / Schir, it is wrang, that for the Father is gilt, / The s•ikles sone suld punist be, or spilt.
From P. R., "The Lamentatioũ of Lady Scotland Compylit be Hir Self Speiking in Maner of ane Epistle, in the Moneth of Marche, the Zeir of God. 1572" (1572):
Now drink thay Mylk, and Swaits in steid of Aill, / And glaid to get Peis breid and watter Caill, / Quhair sic wer wont to ryde furth to the weir / With Iak and Sword, gude hors Knapscall & speir / Quhair sic wer wont brauely to mak thame bowne / With Lord or Laird to ryde to Gurrdwis towne, / Quhair sic wer wont at all Games to be reddy / To schuit or loup, for to exerce thair body, / Now mon thay wirk and labour pech and pant / To pay thair Maisters Maillis exhorbitant.
And from "The Proclamation of the Crying Doun of the New Plakkis and Hardheidis" (1575), published in Edinburgh:
The Regentis Grace, and Estaitis assemblit at this present Conuētion, hauand consideration of the great Inconuenientis that now procedis amāgis our souerane Lordis liegis, in default of victuallis and all vther Merchandice and gudis that is put to derth, and raisit and put to exhorbitant prices, and haldin and abstractit fra Mercattis throw occasion of great quantitie of fals counterfait money, Plakkis and Lyonis vtherwise callit Hardheidis, strikin in cuinʒe in the time of the gouernament of the quene drowarier and Regent our souerane Lordis guddam of gude Memorie, as alswa be fals Cuinʒeouris, not allanerlie within this Realme but als out∣with the same, sa subtillie and in sic forme of Mettall, that it is verie hard to the Ignorantis to discerne and knaw the trew fra the fals.
The first instance of exhorbitant by an English author appears to be Lewis Lewkenor, A Discourse of the Vsage of the English Fugitiues, by the Spaniard (1595):
Neither is the condition of the poore citizens or townes-men any better, who being forced to receiue garrison, and to lodge souldiers in their houses, imparting to them the best chambers and commodities of the same, neuer hearing from them anie other word, especiallie if they please not them in all their exhorbitant demands, than Perhamengo, Lutherano, Borchio, &c.
Lewkenor is described at Find a Grave as "a[n] English courtier writer and soldier also served as Master of the Ceremonies to King James I of England," born in West Sussex an died in London.
It seems highly likely that the variant spelling exhorbitant first arose in English in Scotland, given that the earliest seven (or eighteen, depending on how you count them) publications that use the spelling are from that country, according to an EEBO search. After 1595, however, instances from England dominate the results.
Companion searches for "exhalt*" and "exhon*" (as in the variant spelling exhonerate) yielded no such skewing toward Scottish sources in their sixteenth-century results, so the popularity of the spelling exhorbitant in Scotland during the 1500s (and perhaps earlier) doesn't seem to be part of a larger tendency among Scottish writers of that period to add an h after the x in words that begin with ex- and follow with an a or o.