I've seen random maps generated with vast unusable areas before, and one map where one player was ruined because the only way out of his very small starting area had a very powerful wandering monster stack. By the time he could have upgraded enough to beat it (assuming week-over-week growth didn't keep it ahead of him), all the other players would have expanded and developed healthy economies. I don't recall if I've ever seen a map where there was no way (other than magic) to reach another player.

Stone liths can take you to places you haven't seen, but can only take you to other liths of the right type. If all the liths of the right type are in places you've been, you won't be able to visit new places by accessing them again. There is a spell "Dimension Door" which can move you to any passable tile that is visible while the view is centered on the casting hero. If the impassable area is big enough, this distance limit will prevent you from crossing it. There is a spell "Fly" that will let you treat all tiles (except underground walls) as passable for the purpose of pathfinding, but you must end your move on a naturally passable tile (not water, or mountains, etc.). If your maximum per-turn movement is not enough to cross the impassable area in a single flight, then this also will not help you. There is a spell "Water Walk" which will let you treat water tiles as land tiles for the purpose of pathfinding. However, like with "Fly", you must end your turn on a normally passable tile. There is a spell "Summon Boat" which can, under the right conditions, create for you a boat even if you have no shipyard. If your enemy is on the far side of an ocean, and you cannot get a boat, you could create one magically, then set sail to face the enemy.

[Edit: added the italicized text to clarify the rules for Fly, and mention water traversal completeness.]