One of my all-time favorite is a game called X-Com from 1993 (called UFO: Enemy Unknown in the UK). It's basically a turn-based tactical strategy game. Perhaps its most defining feature is almost completely-destructible terrain. The gameplay ends up being very similar to the Israeli invasion described in the article: using the doorway is almost always the wrong choice. The computer will have the door covered. If you knock through/down the right wall, they have to spend the rest of the turn with their guns pointed the wrong direction (the game has overwatch) and their backs exposed. The most powerful weapon in the game does just enough damage to knock a man-sized hole in the side of a UFO; the qualitative change in gameplay is significant. Those corridors are twisty and treacherous, but entering from the middle instead of the start turns the advantage around.
The other game I thought of is the Splinter Cell series. Pandora Tomorrow, the second game, gave the series a very asymmetric multiplayer style of spies vs mercenaries. In addition to wildly varying, and anti-complementary, abilities, the two sides were practically playing on different maps. The spies could fit in air ducts climb over fences. The mercenaries could only navigate around in the "normal" space of rooms and doors, but effectively owned the places where they could walk, on account of automatic weapons. The result was effectively two maps, one wrapped around and between the other. Even before I was exposed to the idea of scripted spaces, the idea was mind-bending to me. After reading the article, it's even more impressive: one side in the asymetric conflict has an architectural advantage, balancing against its comaprative weakness in more traditional areas. I was never any good at the multiplayer, but it was still fascinating.
Chaos Theory, the third game in the Splinter Cell series, also had some impressive work in the single player. It's the first game I've played where using a non-traditional route like a duct or a drophole actually felt like I was hacking the level rather than following the route that was laid out for me. Games have been using air ducts since Half-Life, but whenever they're available it feels like you're supposed to use them, often because you have no other choice. I feel like I'm finding the way to advance the level. It's difficult to describe, but the holes in the environment felt more natural, like I was following real-world logic rather than game-logic.
I haven't played Mirror's Edge for myself, I would be interested to hear people's perspective on how original that game's use of space is.