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
First of all, there’s no real need to pin down a specific size of paper, or type of material/medium for that matter. You'll adapt to what is needed at the time, just make sure you have options available. I've played various games using A4, A3, A2, whiteboard, a TV screen and at one point a glass table on which we drew with whiteboard markers while using cheetos and funions as props. And I can truly say that these are all great options, except for the props getting 'lost' on that last one.
In determining a good size or the most suitable type of material/medium, there are a few things to consider;
TL;DR: I'd go with A2, but there are other options altogether.
Miniatures & Party size
Miniatures force you to go big in terms of the map's physical size as you cannot really scale down. And of course, the number of PCs you need to accommodate is also going to drive up your requirement. Using smaller tokens or just marking player positions has never really worked for me, it just isn’t the same. When drawing at 35mm scale, you will run out of room on A3 sooner than you think. That is especially true when your players get tactical, which brings us to;
Boundaries
It sucks having to pause the action to add additional sheets because one of your players wants to see whether he can circle around ‘those trees to the side’. Some GMs would say; “Well, that’s just the map boundary.” Come on, really? I prefer to avoid this type of ‘confinement’ and have the players feel like there is an actual world outside of what has been drawn. If there’s a group of trees, of course they can go around it to sneak up on someone. Just don’t blame me if at one point an NPC has the same thought... → See my additional remark at the bottom.
This is why I usually advise people to go with A2 size when using paper. Large tear off pads are affordable and available at any office supply store. Even if this seems big at first, trust me and just start in the middle. Don’t fold them over to make room, you’ll regret it!
Option B
There are other choices if you are not dead set on using paper, but it depends on your set-up. By which I mean the actual table at which you are playing. If there’s enough room so that players won’t be leaning on or putting their drinks/food on the edges of the map, you might consider putting a whiteboard on the table. These are available in sizes more than large enough for any battle and are perfect for drawing on the fly because mistakes a easily corrected. Even better is a smooth synthetic tablecloth, they are available in white but you can also go with transparent as long as you put something under it to provide contrast. You can draw on them with whiteboard markers and they clean very easily.
Additional thoughts on roaming players
The way I go about handling it is best compared to how you can roam about the Battlefield multiplayer maps. You are confined to the general battle area although you can still see a large rendered world beyond that. A player that leaves the immediate area of the battle not only risks being at a tactical disadvantage due to losing line of sight, he risks not getting back in time in case the battle goes pear-shaped. If your map is small enough for him to not run those risks, you should give him some leeway and expand the territory.
When I do not feel like adding additional paper or expanding the drawing, I discuss what the player is trying to achieve and give him the parameters. If he for instance wants to flank as per the earlier scenario, I just tell him how long it will take or what the distance is, what he encounters and where he'll pop up back on the map. Sometimes I also add an additional risk by declaring a 20% chance of attracting unwanted attention or running into an otherwise dangerous situation.
If this still results in your players wanting to explore more than the map you have in mind, just sit down with them and discuss their intentions. Outside of battle or when I do not feel like unnecessarily expanding my drawing, I mostly just describe their surroundings in detail so they can roleplay until they hit a point where they have an encounter with someone or something and it is important to know who is where exactly.