Lobo - It's possible your lighters are experiencing vapor lock. Open the lighter's refill valve and let any remaining fumes out to equalize to atmospheric pressure. Give it a small shot of butane and let it all out again. Then refill to full capacity.
If you're still getting the same result, most likely the little air holes surrounding the main center jet are clogged, most likely by burnt residue, pocket lint, etc. This happens especially with jet type lighters. You'll probably find that giving a hard, concentrated blow of air will get it working a little better for a number of lights, but a fresh can of compressed air will work better. If things are really dirty in there, disassembly and cleaning are fun, and not hard to figure out.
Some of the other suggestion people have made are good as well. Cool the lighter, and warm the refill can in your hands (especially when more than half empty), use true disposables in public places, etc.
BTW, I believe Zippo butane is NOT triple filtered. Vector (owned by Prometheus, which is owned by some other co.) is great stuff, as is Blazer. Might be harder to get, but much better than the Zippo stuff.