I have also experienced this occurrence, otherwise-quick-to-respond gas appliances (stoves, but especially water heaters) becoming slow to ignite after not being used for several days. It happens whether or not the gas shutoff valve is closed, though the effect is stronger/quicker when it is. Hank's suggestion above is actually correct, this occurs because a portion of gas inside the terminal end of the pipe (after the last branch into another house) gets slowly replaced with air. It is true that pipes are under positive pressure, but that does not preclude diffusion into and out of the pipes; it just means diffusion out of the pipes occurs at a higher rate than in the reverse direction. So, if you have an even very small leak from some valve of an appliance that doesn't close completely, this will allow for some gas in the pipe to be replaced with outside air. Since outside air has essentially no natural gas, this means that, over time, unflowing gas in the end of a pipe will be gradually depleted and replaced with air.
[Editors note: converting second answer to an edit]
Thanks Daniel, for your welcoming reply. Just to extend on my previous answer, and as i don't possess enough score to comment yet, i'll note here that you are right that a properly-sealed system will not allow for gas/air exchange; however, i assumed in my answer, as you can see, that there will be some imperfect sealing somewhere along the way (ie, after the shutoff valve), as it most often is the case, mostly in the appliances themselves rather than the actual pipes.
In case anyone is curious, i'll add here that when you have two reservoirs of static gases (such as the atmosphere and the pipes), the ratio of diffusion rates of each gas into the other reservoir increases exponentially (roughly) with the pressure difference between the reservoirs. So if Rg is the seepage ratio of gas out into the atmosphere (in units such as molecules/second, or equivalent), Ra is the infiltration rate of air into the pipes, and Pg is the pressure inside the pipes while Pa is the atmospheric pressure, then:
Rg/Ra = K^(Pg-Pa)
Where K>1 is some constant that depends on the mechanical properties of the gases (their respective molecular weights, etc). This is of course a very rough approximation, as both natural gas and air are a mixture of different gases with different properties.
So when the inside and outside pressures are the same, you get equal rates of diffusion in both directions, as you'd expect, but diffusion into the pipes doesn't cease as soon as there is positive pressure in them; rather, it slows down dramatically, but it is still there. Since the gas coming out dissipates immediately in the atmosphere, everything that goes in is air, which slowly but inevitably replaces the gas inside.
