Typically having possession of the negs is good enough evidence that you have the right to make reprints. Yes, you could have stolen them, but it's not up to the counter people to enforce that law. Any tranfer of copyright comes with paperwork, contracts, or at least a receipt, which should be proof enough.
I wish that professional photogs would mark their photos, but they are still copyrighted even if they are not. The reason Walmart, and many other places are skittish about this is because they have been successfully sued numerous times. Copyright law is very clear, and the fines are very big (can be in the millions of dollars). Claiming ignorance has not proven to be an effective defense, so their employees are trained that when it doubt, don't reprint it. Even if someone illegally copies something at an unmanned photo kiosk in the Walmart store, they are liable.
If you have problems at an econo lab, go to a pro lab. They are used to seeing amateur photos of higher quality, and are pretty good at telling whether something can be legally copied or not. Also they may have waiver forms on hand that would allow them to copy something they think may be copyrighted, but aren't sure about.
If you get busted for speeding, telling the officer that you were late probably isn't going to get you out of a ticket. Just because it is inconvenient to get the proper permission, doesn't mean it's okay to break the law.
I give my wedding clients the right to make as many reprints as they want for themselves, friends, and family for personal, private use only, but I retain all copyright. If they want to use a photo in a commercial manner they need to talk to me. My contract states this, so if they have any problems they can just show the wedding contract, or have the lab call me.
On other jobs I don't give this permission, and I'm glad that the folks at the labs are looking out for my property. There is no difference between illegally copying a professional photographer's photos, and stealing from a shop owner. If you don't like the provisions of the deal the photographer offers, then don't hire that photographer. It's not okay to agree to the terms, and then decide to break them because they are inconvenient later.
I'm not trying to be a hardass, but this is how I make my money. The photos I take are my creative property, just like if I were a writer, a musician, or a software programmer. In this day and age technology makes it so easy to reproduce these things that people rationalize that it can't be wrong, but it is. If my clients illegally reproduce photos they are stealing from me and my family.
http://www.copyright.gov/
Check out this link for USA copyright info.