I believe you just missed few small details about your world:
- We know, that the magic works so good, that airships can fly - and we also know, that that blind+deaf+mad Matt from the other city cannot be communicated to - so we know, that not literrally "everybody" must believe it, but that it is fully sufficient, if large enought majority beleive it.
- There is also the problem, that only we talk in understandable language, so even if there is a lot of nations, that cannot speak right and so are not able to understand such ssimple facts, as that "airships can fly", those airships really fly - as we can see everyday. So it is just logical, that there is needed the vaste majority only locally, not over all world (from which the more was not yet discovered, if we assume something like midlleage)
- we all know, that strange things can happened in undiscovered areass and theier near proximity - some even say, that airships are more prone to crash there for (yet) unknown reasons.
If the world is in magical era comparable to middle age and is comparable to Earth somehow (not just one small island on planetary wide ocean), that for the effect is enought to have majority on some local place, to have the effect mainly working there.
Logically it is possible to came with new ideas and "prove" them to public.
- We need creator, with some idea and some resources (the Guild is not cheap).
- The Guild have "scholars", who are able to "judge" the idea and found "rational core" in it.
- The Guild have also "childs", who may be little young and/or naive, but are willing to listen.
- The guild have also "reporters" (or Evangelists) who spreads the true.
Our creator got Idea "big ship flying in the air". Nobody would trust it now, but the sscholars are good at negotiation and while "everybody knows big ships cannot fly" they came with fully reasonable view, that the creator may just little exgregate and had seen small ship not falling too fast - looking at dirt in the wind, they can talk to children, that they know a man (the creator), that had seen something like ship flying in the air - hey, in such wind as today surely could small ship like this leaf fly in the air, is it not nice idea? And what you think, how it would manuevre - would there be some sails, or would there be some paddles - our loved hero Guily-Where would then today meet some small nation, which fly such ships and now lets hear, what interesting he had seen there ... (later, when Guily-Where is in middle of story on miniship) hey, did not somebody had seen something unusual? And yes, two child have the feeling, they had seen something, which could be a small flying ship, or maybe something toally different... Next day reporters are going around talking about two witnes in Guild, which had seen something like verry little ship floating in the wind. And that all witneses of something flying in the wind, which could ressemble really small ship should go to scholars and say, what they had seen. And each such witness will get copper coin for the effort of reporting. So many people will get copper coin for reporting something not totally different of small ship like shape they may had seen for moment in swirtling dirt on some ocassion. (And talk itself to "maybe it was not exactly flying ship, but it could look alike at least for moment, I want my copper anyway" - and after getiing really paid it would go to "I am not bad person and cheater, and if they get it, there really must had been something looking like flying ship" - and we are there - "flying ships" are "reality", the problematic part is only if what was seen was they or something else )
So next round are schollars writing lot of reports of some sstrange things seen in the wind and childs are presented with the fact, that many poeople reported so seen something similar. And instructed to study all those report and make opinions about that and raport anything similar they thing they had seen, even if not totally clearly. Soon each child would strongly beleive to seen something and all people in vicinity are informed, that the Guild is heavivily studining small flying ships with many probable reports written down. And anybody is encouraged to help and report what he thinks about how that ships do manuevre in the wind (with usual copper coin for report).
Next round there is a lot of interesting possibilitiess, how to navigate ship in wind and childs are working on (and counting and voting), what is more usual navigation method. (Hey, now we have all childs beliving in small flying ships, lot of people around beliving they hade "seen something", everybody around knows, that guild is seriously researching small flying ships and had a lot of reports and witnesses, and according to their research the most common method of manuevring is this and that - as reporters say to anybody, who is willing to listen.)
In the guild childs do paper models of most popular (voted on) design, and drop them to wind to see, if they fly (and they do, partly as they are light and wind is strong, partly as everybody around is starting to believe, that is is possible). Reporters talks about "many ressearch projects, whit different result in practice (and do not talk about the reluts ranges from 1cm to 2m before hitting groud and be destroyed). Also offers "artistic pictures" of most promissing models (drawn in bright collors and decorated stylized silhouets of Guily-Where and his friends - just to fill free space, not to exact proportions) - there will be voting on popularity of such artistic impressssionss, and from those, who will voted for most popular design, would be draw 3 random "winners" which will get ssilver coin each - so there will be probably lot of people voting (and half believeng in possibility of maybe small-men-sized flying ships - hey I really wish to be a winner and get a silver coin).
There is secretly build ramp in woods near a lake and the winning model is made large to fit a child. With high enought (an long) ramp, collected winners and child and more enthusiastick commonners it can be done "prototype testing", which results of (balistic) flying those ship say from 1 meter bottom of ramp to the lake, where it would hit watter after like 2 meters, but we will measure also the place, where the model would stop moving against watter. With local 100% majority we should be able measure like 10 meters for winner (winning big cake) and say, the testing was generally successful, it have stil some small problems, but principially it WORKS. (not yet much magically, but anyway) - reporters would talk about Guild testing attacked two digit distances of total fly, name the "pilot" and talk about his/her bravery. And that Guild is deciding much larger ships to release soon, just when found small problems will be solved.
And now we have lot of eye witness, much more, who had hear about it from many sources and all know, that airshipss can fly and Guild is working on much larger and better models.
So we build at least one, hide it under tent with all events pictured by artists (based on reports of direct eye witnesss) and we can start travel around near vilages, presenting, what our "scholars" are "developing" in the Guild and what may be soon used in everyday life (when we fix out all small glitches)
And we did not even lied, just used sugestive questions, precissely directed missinformations (ommiting inconvenient details), exgregations and positive loop for getting better results (and cummulating convenient errors). We have lot of believers, many eyewitness, some pilots and nearly working model ready to use, when we reach majority on large enought local scale.
We are sure, that it will work, because we know, how the magic works here (so the knowledge works for us, not against us) and even now it works "somehow".
Few such action and we get to the point, where "everybody knows", that "everything Guild does" would work. Then we can start round corners and skip smaller steps. It would work anyway, because "everybody knows, it will". And we believe in our success too.
Next we just need improve reporters and learn better to write ideas from "maybe it happened one time somewhere without witness" to get faster to "they sasy it works in Guild hidden test Area 42" and finally "everybody is talking about how big success it will be, when presented for real"