Mildly inspired by this slightly vanilla-y list.
Mine, I think...
1) Souffle Continu, Paris - I think my love for this is based on the owners as much as anything. But it is a great store, has such a great CD collection of all kinds of oddities. My go to place for anything worthwhile, along with a chat about whatever's new. Such a shame they're shifting to vinyl. http://www.soufflecontinu.com/index.php?f=accueil
2) Sounds of the Universe, London - Only recently rediscovered it. Absolute treasure trove. I love the labels on all the albums though, and the downstairs bit full of coffee-table books and weird 2nd hand jazz.
3) Bimbo Tower, Paris - In terms of eclecticism, can't be beat and if you know your jap rock I suspect it's heaven. I love it but rarely go there these days. Great world music type section and I have never seen anyone shop stock so much Muslimgauze. However, find it a bit too cluttered to find everything and they don't turn the stock over enough to make it worthy of repeat visits.