i don't know about the CBD but i was recently in Melb. you could go to the Obese Records shop in Prahran they got some records there but a real dope place is like 10 metres up the street from Obese. i can't remember the name of the place now it's Greville Records or something. they got a nice collection of stuff, decent prices too. i'm movin there next year so hit me back if you find any other good places.