I've run a few campaigns to level 20 now, not sure what I do different but I don't find them that much more difficult to balance than mid level games. I do use the alternate rest rules, so it's easy to push resource expenditure; I set up scenarios where they simply can't take a week off to recuperate and recover*. So go ahead cast that 9th level spell, it's going to be a while until you get it back.
Scrying and teleport can be countered fairly easily by the high level opponents the PCs are tracking. Even then, scrying doesn't necessarily tell them much. Yep, you see the target from a drone up to 10 feet away. It doesn't reveal their location unless something happens to come into focus. Odds are they aren't doing anything of interest in the 10 minutes the spell lasts unless I want to reveal information to keep things moving. While I limit teleportation and plane shift for multiple reasons, there are also permanent spells that block those spells as well.
Combat encounters are always something that you simply need to know the capabilities of your group to judge. Throw an ancient red dragon at a party where the wizard always preps fire spells to the exclusion of all other types of damage and the group may have a bad day. I try to mix things up now and then, throw multiple enemies from multiple directions, put opponents in that will be challenging and fun for all the different PCs to engage. I also make custom monsters, such as doing things like doubling attack bonus and at least doubling damage for relatively low level creatures while not changing anything else. So they're not minions, which never made a lot of sense, but they fit the same concept.
I could go on, if you care I wrote up the following a while back
Anyway, those are my thoughts on the general topic. I don't really have a solution for the travel hither and yon aspect, other than to occasionally bring it back home. Combats will often take longer, a lot of it just depends on players. As much as I give advice and options for players on how to resolve their turns faster (e.g. roll all dice at the same time, roll ahead, remind people they're next so they can plan ahead, use average damage and so on), some people are resistant to doing anything different.
Perhaps consider breaking up combats sometimes? The BBEG flees and there has to be a skill challenge or other obstacles while you hunt them down? That may work better in my game because the alternate rest rules apply to PCs and NPCs alike.
In any case, good luck! I've had a lot of fun with high level campaigns, it lets me as a DM just go gonzo and throw all sorts of crazy stuff at the group and have fun as they figure out how to defeat my over the top adversaries.
*I kind of wish there was a way to take a partial long rest to get some long rest resources back, it would help balance out short and long rest classes for me. But that's a separate topic.
Scrying and teleport can be countered fairly easily by the high level opponents the PCs are tracking. Even then, scrying doesn't necessarily tell them much. Yep, you see the target from a drone up to 10 feet away. It doesn't reveal their location unless something happens to come into focus. Odds are they aren't doing anything of interest in the 10 minutes the spell lasts unless I want to reveal information to keep things moving. While I limit teleportation and plane shift for multiple reasons, there are also permanent spells that block those spells as well.
Combat encounters are always something that you simply need to know the capabilities of your group to judge. Throw an ancient red dragon at a party where the wizard always preps fire spells to the exclusion of all other types of damage and the group may have a bad day. I try to mix things up now and then, throw multiple enemies from multiple directions, put opponents in that will be challenging and fun for all the different PCs to engage. I also make custom monsters, such as doing things like doubling attack bonus and at least doubling damage for relatively low level creatures while not changing anything else. So they're not minions, which never made a lot of sense, but they fit the same concept.
I could go on, if you care I wrote up the following a while back
Suggestions:
Specifically for higher levels, things that I do are (I mix and match the below a lot)
- Use better tactics. Take advantage of cover and environment. For example small foes can use small tunnels with tiny openings that are too small for medium size creatures to go through.
- Send waves. At higher levels wizards can do a lot of damage, so don't send all the foes at once.
- Flank. Related to sending in waves, have weaker foes run in from the obvious direction while the real foes come around the back
- Illusion. That BBEG? Well it's an illusion. The real BBEG is hiding around the corner. Note if a target isn't legitimate for a spell, I don't make the caster expend a spell slot. So if they try to banish the illusion it doesn't work but they also don't use the spell slot.
- If fighting animal intelligence monsters, they're likely just looking for food. After a PC is knocked unconscious, take them off into the bushes to be eaten in quiet.
- Number of combats between rests. It really does help to have 6-8 encounters with only 1-2 short rests. I use the alternate rules where a short rest is overnight and a long rest is a week or more because it works better for my campaign pacing. But if you have multiple fights, the wizard is going to hold off on that meteor storm until it's really effective. We also frequently have multiple game sessions without a long rest - people do need to take notes of where the left off.
- Obstacles/goals other than killing stuff. Too often it's go there kill the bad guy. What if you have to instead save the prince? What if your could survive but the prince is squishy? How do you protect him.
- Use custom monsters. Follow the guide in the DMG to make new monsters, they're frequently much tougher than what's listed in the MM. Or depending on budget look at 3rd party books like Kobold Press's Tome of Monsters.
Specifically for higher levels, things that I do are (I mix and match the below a lot)
- Monsters have advantage on a regular basis. I justify it multiple ways, or just secretly roll it.
- Do more damage. Not just more damage, but more types of damage. Particularly useful for my wife's half-orc character that has resistance to weapon damage. The BBEG has a sword made of lightning.
- Attack more. Bonus actions or just multiple attacks.
- Attacks that do more than damage. Taking people out of the fight is boring, but restraining them with a giant tentacle that is slowly crushing them? Go for it.
- Transformations. This one is a little trickier (and to do justice would take more time than I have) but instead of making monsters big bags of HP, have them change at certain points. At a 2/3 of their HP they lose some AC but start blindly flailing getting more attacks at a bonus. At 1/3 their HP their acidic/demonic blood is spraying everywhere causing automatic damage (or constitution save for half). When they die they explode.
- Spiritual allies. Instead of giving a monster minions that can be killed, they send out spiritual allies (inspired by a cleric's spiritual weapon) that can attack as a bonus action
- Counterspell. This one can be annoying if overused, but give the enemy casters counterspell. If you really want to be mean, the enemy caster is a sorcerer that can cast without verbal or somatic so their counter can't be countered.
- Ranged attacks. Almost all creatures have effective range attacks or can get to people that are flying away.
- Different saves. I make up a lot of monsters. So sometimes it's going to be strength saves, sometimes it's going to be intelligence and so on. I don't pick on individuals, but I do try to vary what I'm targeting.
Anyway, those are my thoughts on the general topic. I don't really have a solution for the travel hither and yon aspect, other than to occasionally bring it back home. Combats will often take longer, a lot of it just depends on players. As much as I give advice and options for players on how to resolve their turns faster (e.g. roll all dice at the same time, roll ahead, remind people they're next so they can plan ahead, use average damage and so on), some people are resistant to doing anything different.
Perhaps consider breaking up combats sometimes? The BBEG flees and there has to be a skill challenge or other obstacles while you hunt them down? That may work better in my game because the alternate rest rules apply to PCs and NPCs alike.
In any case, good luck! I've had a lot of fun with high level campaigns, it lets me as a DM just go gonzo and throw all sorts of crazy stuff at the group and have fun as they figure out how to defeat my over the top adversaries.
*I kind of wish there was a way to take a partial long rest to get some long rest resources back, it would help balance out short and long rest classes for me. But that's a separate topic.