We did the Portugues in 2009 from Porto and got our credencial in Porto and our first stamp. What the peregrino office in Santiago wants to see is that you got stamps that state the name of the place and that the date is written in. They are not too picky about where the stamps are from. You can go into bars, hotels, restaurants, post offices, police stations, municipal offices and even gas stations to get stamps (and of course churches and albergues). On the French route, everyone on the route had a stamp. On the other routes, they are less frequent and so bars and restaurants might not have one, but all public offices will have something and they will all know about peregrinos. What you are looking for is called a 'sello'. So you might see a bar or cafe with 'tenemos sello' outside of it. If you walk into a municial office, police station or post office and show the person at the desk your credencial and ask for a 'sello' they will know what you want.
There is even a website out there where someone asks people to send in their sellos from the various caminos.
Buen Camino