A buck-boost regulator comes to mind. Haven't actually done one myself, but I've had good results with a small boost converter (MCP1640) in a circuit that requires right around 100mA at 5V. It can use two or three alkaline or NiMH AA cells. Haven't done a real good test yet, but it looks like two fresh alkaline cells should run it for at least 8 hours, three should give half again that. Makes a lot of sense to boost a lower voltage when it can be done at 90%+ efficiency, as opposed to knocking it down with a linear regulator and wasting power. A lot of the switching regulators these days don't require complex circuitry. Build it on a PC board, keep things close and traces short and you're off to the races.
I definitely would try to avoid the scenario of running a regulator (or most anything) out of spec.