The DM who's started running in my Monday night group uses
Post-It Easel Pads and has the maps pre-drawn. I've bought such a pad myself, and plan on using it when I get the opportunity to run.
The DM leaves his maps in the pad, and flips it to a new page when necessary. However, I would tear them out personally, for the ease of transition.
In our 3.5 days though, we did have a dry-erase battle mat (one side was squares, the other side was hexes). That wore out after time, as the lines never fully erased 100% (more like 95%) and wear and tear left it more messy looking over time. Personally, I would prefer the large grid paper and pre-drawn maps for the sake of clarity and saving time in-game (since you won't need to draw it out on the spot), but its something you really need prep time before game to make work.
As for the multiple dimensions issue, having one half of the paper/map/mat be one level, and another half be another level, would be your best bet, IMHO. Like in City of Towers with the Mourning Haunt battle.