Lumens can be a bit misleading. Sometimes they are rated as OTF (out the front), and other times its the max output of the emitter. This ASSUMES the emitter is driven at maximum, which isnt always the case.
Some simply lie like crazy. Many of the multi-5mm led lights have high lumen ratings but are crap compared to a 'real' lioght.
The key is that the lights discussed here use much more efficient emitters. That means that with 2 AA batteries (3 volts in series), at 1 amp = 3 watts of power. A bit less due to driver efficiency loss, but with emitters able to produce close to 80 lumens per watt or more, you can see that even a small battery can provide decent illumination.
My recommendation is to look at Romisen and itp lights at goinggear.com. His site makes it very easy to browse lights by manufacturer. You can likely find something for 20-30 bucks that you will like a lot more than anything you could get at walmart.
As an example, my 25 buck itp A1 uses ONE RCR123 (half the size of an AA), fits on my keychain and can crank out 200 lumens! Crazy. A light that uses CR123s is probably your best bet, since they have the highest energy density and voltage. You can get a good sized pack of them online for fairly cheap.
An alternative is to invest in rechargables, which is more of a pain.
You might even consider one of Romisen's flood-to-throw lights. Didnt see it on shiningbeam, but check out...
http://goinggear.com/index.php?main_page=product_info&cPath=14_48&products_id=426
Romisen RC-C6 Focusable Q5 LED Flashlight. It says 180 lumens, but this is likely exaggerated. More like 120 for real. That said, the ability to go from a wide flood beam to almost pure throw (narrow beam) is really cool and makes the light a lot more useful.