Cut a bigger battlemat down to size
A straightforward solution would be to buy a standard battle grid, like this one from paizo, and cut it into smaller pieces using sturdy household scissors, x-acto or carpet cutter knives.
The main benefit is that this works exactly like the big one with regards to what pen you can use or how to erase it.
The paizo one (and presumably others), comes folded into thirds, so if you cut it along the folds you get 9 pieces of 8×10" (≈20×25cm). Personally, I'd probably want to get rid of the old folds completely if it doesn't lie flat, so I would add some margins to the cut, making the maps just a little smaller (and the edge squares slightly non-square).
Also, I suggest keeping a 2×1 (i.e. 16×10") and a 1×2 (i.e. 20×8"), as well. With only a single fold, these pieces should easily fit into a normal notebook without being to bulky, and they will come in handy for medium-sized rooms and hallways.
Field test results
I went ahead and tried it myself. I used the flip mat that came with the German version of the Beginner Box. It's the same size as all paizo mats (30×24"), and as far as I can tell by direct comparison, the material is the same as with the paizo mats (unlike certain, incredibly ugly green pawn feet...)
I decided to cut the 3×3 into three pieces: a 1×1 (8×10"), a 2×1 (16×10") and a 3×2 (24×20").
I tried cutting it using a metal ruler and a carpet cutter, but I realized my carpet cutter is completely dull (I wisely tried it on a corner of the map first). I then opted for a good pair of scissors instead. I used one side of the crease as a guideline, and it went quite smoothly. I then proceeded to cut along the other side of the crease as well, cutting away about 2mm from the edge.
Examining the pieces, I can see no fraying at the cut lines, and honestly can't tell the "new sides" from the old ones. I tried fraying a corner with my fingernail, and that works the same on all corners as well, which makes sense, seeing that the whole map was cut from a bigger piece of printed cardboard in the first place. That being said, if you don't cut away the creases, it seems to fray quite easily at those edges (presumably due to the increased strain). This may or may not "spread" to the rest.
Overall, I am very satisfied with the results, and I'm sure the smaller mats will come in handy for smaller tables.
Here are some pictures I took with my magic potato (click to enlarge at your own risk), the folder and the 30ft. cone are for scale.