As I'm travelling a bit these days I searched for record stores in some cities. So I stumbled upon this group from discogs where people recommend shops for most cities and it's really helpful. I even discovered some stores in my own city Just type in any city in the search field to the right.

http://www.discogs.com/group/476

Only downside is that some of the topics are quite old and you can't answer if the last post is older than a year so it might be that some stores don't exist anymore if you're unfortunate.

super cool.