If your patches are lasting one minute, you're doing it wrong. I have tubes patches upwards of ten times, (I could patch them more, but I just get lazy after a point), and they are no more likely to fail at a patch than at any other location. A good patch is a permanent repair.
Of course, you are right about large box stores, and even most small towns will have one bike shop. Plus, chatting with local bike shop owners is a great way to find out about local routes.