I used to live there years ago and used to like 'Les Mouton a cinq pattes' excuse the lack of correct accents but I can't find them on my keyboard right now. It's in the Marais area (4th arrondissement) if I remember correctly, and used to have a great selection - but I haven't been for a vintage shopping trip there for a while - so it's highly likely that it may no longer exist! Some other trendy, young vintage stores, (can't remember names at the moment but will think), around the slightly tacky Forum des Halles area - more along the collectable denim, retro, trendy stock type rather than high end vintage if I recall - but worth a look.
However I have been to the flea markets more recently which are legendary - not always the cheapest, but some amazing things do turn up. I can recommend several and have a great book which details all the regular stallholders at each one, which is invaluable - but won't do that here in case it's just B&M stores you're after.