To the two folks who mentioned Rock Box in Camberley, you from round that way then? I used to go there occassionally in my teens and it was the best place in the area definitely. I'm from a few miles down the A30 and went to school nearby in Yateley. What about you guys?
Oh and to add weight to the Nottingham tips, now currently in my 5th student year there I can back up all the props given. Selectadisc is the Mecca of the city and you can always find something you want at a decent price. They used to have an excellent second hand place a couple of dorrs down Market Street but apparently it wasn't making money so they closed it down. Shame because I got some crackers for next to nothing there. And Rob's Record Mart is a hidden gem, tucked away down Hurt's Yard, a tiny alley with records and CDs six feet high and no room to move. Fuck knows how he keeps any semblence of organisation but credit to the man.
I also found the Oxfam Books and Records shop towards the lace market the other day and whilst not that comprehensive it's worth a look because you might find something you've been looking for and hey, it's for charidee.