Have you considered spells that mask an area from the
Scry part of "Scry and Fry"?
Some create a false image of the area, some block the Scry.
There's also spells like
Mind Blank, or the ever popular "Amulet of Proof Against Detection and Location"
The amulet is not all that effective at higher levels, but the spell is a stone wall against the
Scry. Nothing less than Divine Intervention will penetrate.
Also be aware that
Scry has a casting time of 1 hour. And the Scry Sensor is visible to anyone with an Intelligence of 12 or higher. So you want to use a spell to get a 3 round warning? Based on the DM's ruling you could have up to an hour as the sensor forms and tracks.
Take a look through page 104 of the DMG. There's a section on Villains that gives advice on this exact issue.
Then there's the idea of mundane shielding for an area.
Player's Handbook PP 173 said:
Scrying: A scrying spell creates an invisible magical sensor that sends you information. Unless noted otherwise, the sensor has the same powers of sensory acuity that you possess. This level of acuity includes any spells or effects that target you (such as darkvision or see invisibility), but not spells or effects that emanate from you (such as detect evil). However, the sensor is treated as a separate, independent sensory organ of yours, and thus it functions normally even if you have been blinded, deafened, or otherwise suffered sensory impairment.
Any creature with an Intelligence score of 12 or higher can notice the sensor by making a DC 20 Intelligence check. The sensor can be dispelled as if it were an active spell.
Lead sheeting or magical protection (such as antimagic field, mind blank, or nondetection) blocks a scrying spell, and you sense that the spell is so blocked.
The lead sheeting idea doesn't require that your bad guys be high level or even very rich.
Consider using a
Magnificient Mansion as a resting place. They may be able to
Scry into it, but
Teleport will get them nowhere. You can't
Plane Shift into it because you can't get the Focus, the item attuned to that plane. You can't
Gate into it since you can't name the plane. And looking does you no real good.
There are lots of ways to mess with Scry and Fry