Why would anyone sit on an island while it sinks to the depths?
Because the reason they went there still exists.
Re: OP PCs, I forgot this was 3.5, which I don't know very well. Also that's quite a list and I'm not going to deal with every spell individually. My general response to "scry and die" is to read the scrying and teleportation entries very carefully and assess their limitations. How good a look does the scryer really get of the area, is it really good enough to teleport with accuracy? Is it enough to "visualize" an area for dimension door? How much time does the BBEG spend in his main rooms anyway, ie. when you scry him, what are the odds that he will still be there when you teleport? Can his central chambers - bedroom, dining room, war-room - be in a pocket dimension, like Mordenkainen's Mansion, to make scrying more difficult and greater teleport risky? Can he be in a room that is essentially featureless - at least within 10' of where he is likely to stand - or clouded the area with smoke or steam, making it harder to gain familiarity with the area? Can he have constructed several identical spaces that are filled with poison gas and traps so that it is likely that teleporters will end up in the deadly rooms?
Insulate rooms from passwall by having a cistern or other water hazard surrounding the room - the passwall opens a passage into the water instead of the room, flooding the area the PCs are casting the spell from.
Find traps requires a good hard look at defining a trap. Is appears to be limited to conventional traps that are detectable by "find trap" rolls, so I expect high level dungeon would just not include that sort of trap. Is a hallway full of gas a trap? Is the cistern mentioned above a trap? I don't think so under this definition. You can also make existence of the trap obvious, but the nature of it obscure, like the open, spiked pit that you try to jump over, only to hit an invisible wall mid-air.
The 3.5 version of Find the Path presents a conundrum. It is probably best addressed by ensuring that knowing the path does not help you - or ensuring there is no path to find. Knowing the best way to avoid a trap or hazard doesn't help you if there is no way to avoid the trap, such as something keyed to alignment. And what if there are two paths, both with different unavoidable hazards, one of which is not clearly more better or safer than the other? One can also ensure that the "shortest, most direct physical route" is the most dangerous with unavoidable hazards, and requires that only an indirect, convoluted route be taken to avoid them. Or use the spell against them; the quickest, shortest route requires actions that require the PCs to blow a bunch of spell slots - eg. traps that are are disabled if someone casts a specific spell, the exact spell doesn't matter, as long as it competes for slots with spells that are a problem.
Wind and water seriously mess up gaseous form. True seeing does not help with nonmagical effects. Vision only works if you ask the right question. Many of the divination spells only work if you know who is the target of your investigation, which suggest that the Evil Overlord will conceal his identity, or even existence, or act through a strawman. Or confuse the issue by using polymorph any object to create a bunch of genetically identical duplicates.
Basically, you can construct a whole adventure designed to eat up all of the PCs' divination and teleportation spell slots. Don't try to avoid them per se, just make them use them up. Or force them to fill their slots with other spells.
Re: Anticipate Teleportation, I note it is limited to a 5' radius per level, which does not prevent teleportation outside the radius. So send in assassins who are deposited outside of the area and infiltrate the PC's stronghold - doing significant damage to the PCs' retainers along the way. That included agents teleported above a castle, using some sort of mechanism to fly. If the stronghold is underground, polymorph the assassins into Xorn first.
And don't have the BBEG throw all of this resources into a single assault. Have him test their defences, and learn from them. After all, he doesn't care if his minions die in the assault. The minions die a particular way, ok, he knows you have that
spell and how you are deploying it.
Also, if you prep your situation well, you don't need a bunch of if-then statements, because consequences of PC actions will be clear from the nature of the faction/NPC and the resources available to him.