Chessex manufactures grid maps that you can draw upon, with water-soluble markers ("overhead" pens). These are available with a variety of pre-printed patterns, so you can get those with hexes, squares, and so on.
I personally use a mixture of one of these mats, "dungeon tiles" (tiles of various shapes with terrain pictures on them, plus pre-printed grid marks), printed out sheets for some floor plans and such. Often I place a large plexi-sheet over these: it keeps the bits and pieces underneath from moving around too much, is better to roll dice and move around counters on, and I draw on the plexi with dry-erase whiteboard markers (which are not usable on Chessex's mat material) and cleaning up after these is much nicer than the water-soluable overhead markers.
Also, I use the plexi-map as a cover for a variety of boardgames I have that come with folded up card-stock maps.
To get the sheet of plexi, I just went to a local glass-supply place and gave them the measurements I wanted and they quickly cut me a sheet. You can also get plexi at some large DIY or home supply or hardware places, but I found that the prices were cheaper at the glass supply place especially when it came to just giving them a set of measurements and asking them for a precisely sized sheet.
Nothing special happens by RAW
There are no official rules describing being on or off a map in 4E. Squares, and what might be in them, are defined as game elements, but maps are not.
Technically, DMs that allow movement off map that looks like it should work (e.g. continuing along a forest path) are playing by RAW. If you can move to a location, and it would be a different square on the grid that happens to be off the map, then there is no game rule that says you cannot. There is no game rule that says that you cannot be placed there by forced movement. Nor is there any game rule that says this has any consequence beyond the distances, effect on Line-of-Sight and Line-of-Effect etc that any other location for a character has.
There are reasons to keep game on the map
However, that's not the same as saying the DM has to stop and draw more map - the map is a tool to get the job done, it shows where everything is, and makes it easy to apply the rest of the rules. It may be awkward to extend the map in practice, depending on DM, available space, time and materials.
Combat in 4E is often a set piece with a balanced encounter and prepared battle map. So it helps a little if that is how it plays out because it suits the players and NPCs to engage in the area that you have prepared.
Solutions that avoid invisible walls or running away
I usually have some incentive for PCs to stay on the map, but vary things to stop it seeming arbitrary. Here are a few things I have done:
1) Outside the map is populated by hostile creatures doing other stuff (maybe in the context of a larger battle). Optional: Minions drift onto the map each round, as a reminder that "there's a lot of them out there". Stepping off the map will put you in melee with 1 or 2 minions, adjudicated without using the battle board (I found this discourages ranged characters drifting away to keep distance, something I had a problem with a highly melee-averse ranged striker in the group)
2) There is lots of cover/concealment between on and off map, so stepping off the map may allow you to move around to another location (perhaps an Athletics roll or power required to move around), but attacks are not really possible between the on and off areas.
3) Nothing special happens off the map, but movement and attacks are adjudicated without using more battleboard (DM decides range, cover, adjacency as he or she sees fit). The NPCs have some reason to stay centrally, and enough range or cover, or special rulings so that PCs don't simply win by using ranged attacks from outside the edge of the board. This applies simply enough to many dungeon encounters.
4) The area outside the battle map is hazardous terrain - often the same type features in spots on the battle map. This doesn't have to be anything clever or fancy. A battle on top of a tall building, where none of the combatants has long-running flight, would work quite nicely.
5) The whole point of the encounter is for the PCs to cross the map, and the NPCs are trying to prevent that.
6) I have on a few occasions prepared an "infinitely scrollable" wilderness battle board (using tiles that repeat every 20 squares or so). So the PCs can have a running battle whilst the general terrain remains similar. It's not possible to "leave the map" as such, but I only need to prepare a 20x20 area (obviously this needs to have simple repeating features)
Invisible walls and running away are house rules
Ruling that "you run away if you leave the map" is not RAW in 4E, but may be a reasonable compromise. Yes the PC might gain some distance or cover advantage which could make sense in the game world given what is on the board, but it is not always worth the disruption/delay to the game to support that.
Combat in 4E has lots of abstract elements - the battle board does not even have real-world geometry to start with, and there are many meta-powers that work by controlling the board directly, despite that not making great sense logically. "Step-off-the-map = run away" is a house-rule-of-convenience completely in line with those kind of game elements.
Ways to handle forced movement off the map when there's a house rule
The OP asks specifically what should happen when forced movement pushes a creature off the map when a DM has made a house-rule of "invisible wall" or "run away". In this case the DM will need to improvise. For instance, if I were DM, I might simply place the creature at the edge of the map and require it spent the difference in points of movement to get back to that square before it could take any other action.
However if an enemy creature was forced off the map by use of a Fear-based power, I might rule "run away". I would inevitably rule differently for PCs and monsters because the game consequences would be different. A good rule of thumb for a DM improvising when there is no obvious RAW is to favour the PCs (but not so much that it becomes abusable - review any decisions afterwards). So "monsters run away, PCs must spend movement to return to the board" seems reasonable.
Ultimately you want to avoid silly arguments about the house rule, which is probably just in place because there is no squared paper or space on the table and the DM doesn't want the additional effort of tracking stuff not on the map.
Best Answer
We just ran an adventure almost exactly like what you describe. The party was climbing a stairway that ran back and forth across an underground cliff face (many hundreds of feet tall), while menaced by flying opponents and threats at various levels. Three players were in person, and two on Skype.
Instead of using a dry erase board, our DM built a cardboard stairway that we used to represent whatever section of the stairway we were on. He painted his to look like stone, but it's not necessary. For the flyers, he used lengths of heavy wire, the ends secured to weights and the free ends hooked to the miniatures. The wire is bendable enough to move the flyers to the approximate position.
He had (broken) elevator platforms he could hook on at various points. The concept could be adapted for your plunge pool and wide ledges.
It was a fairly simple model, but it made the combat very memorable. Here's a photo of the model in action: