Re: Niche scenario - but annoying regardless
There's a marvellous new invention I've heard of called a "pocket." Maybe you could get into the habit of keeping a bag in one?
Paper bags - surprisingly - have a worse environmental impact than plastic: they take more energy, and cause more pollution, to make; and they don't actually biodegrade much faster than plastic. Source: http://science.howstuffworks.com/environmental/green-science/paper-plastic1.htm
That's why it's best to have plastic bags which you re-use.