The Cinema Store is pretty great - at least it was the last time I visited. They have two shopfronts, one for mags and memorabilia, the other for books, CDs and DVDs.
IIRC the former has a basement full of older stuff - I saw Kim Newman shopping for laserdiscs there once (a few years ago, not sure if they still do lasers!)
They're here:
Orion House
Upper St. Martin's Lane, Covent Garden, London, WC2H 9NY