Polygons arising from knot diagrams

Colin Adams, Reiko Shinjo and Kokoro Tanaka have a paper (http://arxiv.org/abs/0812.2558) that shows that for any knot you can find a diagram which has only regions with 2, 4 and 5 sides.

I'm pretty sure something like the following construction can be used to transform any knot diagram into another diagram for the same knot in which each region has bounded complexity. I didn't draw the over-under relationships at the crossings but that's not a problem.
_{(source: uci.edu)}

The consensus seems to be that the answer is 4. Here's a simple proof that it can't be anything less (that is, that 3 can't always work). It can be arranged that all vertices have degree 4. Let the diagram have $n$ vertices. By Euler, it has $n+2$ regions (including the outside region). Each vertex takes part in 4 regions, so the average number of vertices per region is $4n/(n+2)$. For $n\ge7$, this exceeds 3. If the average region has over 3 vertices, some region must have at least 4.

Now here's a hand-waving argument that 4 is always possible (presented because I don't understand Ryan Budney's argument in the comment on the question). Find a region that has more than 4 vertices. Take two more-or-less opposite strands bounding that region, and do a Type 2 Reidemeister move on them. That will split the offending region into two regions (and a digon), each with fewer vertices than the original. Unfortunately, it will also introduce two new vertices into the region on the other side of each of the two strands, which may move one or both of them over 4. The hand-waving is that if you persist with doing Type 2 moves you will eventually get to all regions having 4 vertices or fewer.

EDIT: I have lost faith in the hand-waving argument. If you start with a pentagram, which as a knot diagram represents a knot with 10 crossings, 10 triangles and 2 pentagons, then, persist as I may, I keep producing at least as many regions with 5 or more sides as I remove whenever I do a Reidemeister.