Make the storm originate in the Etheral plane like
@Shiroiken suggested.
Have three portals inside the ethereal to elemental plane of earth and air and to limbo for the chaotic aspect of it. It manifests there as well.
You see, that is why I am always so skeptical on handwaving these "trivial exploration gimmicks" which seem to be expectation for every setting (e.g. Fly, levitate, featherfall, Ropetrick, tiny hut, all sorts of teleportation and gating and you got etheralness, wind walk etc.)
In some campaigns they are the topping on the cake and do not cause much trouble. In others they destrpy the whole pillar of exploration and dangerous travel, act like an access all areas backstage pass, a go free out of prison/manacles/ every situation.
Other such spells (with less impact but still diametric to some themes) are have your weapon available all the time /and eventually it is even magic (bladelock), summon free disposable eye in the sky super drone with telepathic radio (find familiar) which in former editions always had some drawback and now are mostly a whenever you so desire thing.
There is also something called an etherstorm google for it, I cannot look it up atm. It would be another alternative to make your storm challenging.
Some standard procedures are fine, like the rogue checking for traps, or a fixed situational marchorder. But if Etherealness is the first thing to for the group to use in every nontrivial travel situation, then you might as well install fixed teleporters at all your campaign locations, it does not make any difference.
To help you more it would be good to know some more detail of your campaign, since it seems to be a reccuring pain for you as DM.
Edit: have some 5th magnitude ghosts going crazy on them for disturbing them in the ether plane all the time if nothing else helps (You have to homebrew these though 5e mm won't help you, just include hefty 4d20 years aging attacks!). Send them to Ravenloft the next time they try the trick "unjustified", maybe they triggered a planar anomaly.
Do only use every hampering theme once, then they cannot complain. Give them a hefty encounter without the possibility to rest, so hefty, that the cleric has to burn his slot.
