For years, we used a few A3 sheets of hex paper that had been laminated. Whenever we needed a really huge battlemap, we just laid them down side by side. It worked well.
If you stick with multiple smaller-sized maps, there's no need for an oversized printer or laminator - you can just print them out and laminate them at the local print shop. They also travel and store more easily than a single big map.
Of course, eventually I started to want something prettier- so this week,
I came up with this.
(Sorry to link to my blog, but I happen to have just posted these new battlemaps, and they seem relevant to the discussion.)