In Paris, it used to be all about L'Oeuf Cube - I think the Metro station is Jussieu, but you might want to check that. Living in the French provinces it was like some kind of mythical Eldorado I would hear about... I eventually made it there and it's actually two separate shops, and the action was really out on the pavement out front with proper Mr Suitcase (or Monsiuer Suitcase) types flogging their wares. I remember getting my first unlimited Sinkholes there, then promptly being bugged at Les Halles. Good times... probably around 1998 or 99 or so.
Still, I imagine it would still be a good port of call for you and they could point you to somewhere to play.
There's not really a central London shop that I know of although there was talk of
http://www.magicmadhouse.co.uk/ opening one I think - not sure if they did, I moved a couple of years ago. Still, the best place to play and trade is the Games Club - especially on Fridays. You can probably get a game of Vintage there actually these days: there's at least three or four guys down there with sanction vintage decks ready to go. You can find all the details here:
http://www.thegamesclub.org/
