I used to listen to the metal shows on community radio and record songs with my boombox, then head to the record stores when I had some cash. My local in Frankston was called Platos, I spent heaps of time in there. Once a month or so I'd head into the city to go to Metal For Melbourne, Extreme Aggression and Missing Link.
Before my time, it had just moved into the Banan Alley vault the first time I went there. It was in the old Gas & Fuel building complex I think, which is now fed square.
Extreme Aggression was run by a German guy called Daniel who also ran a distro called Modern Invasion Music. Most of the old vinyl I had was imported by him.
Missing Link was still going until pretty recently, it ended up merging with Collector's Corner and they had a shop upstairs on Bourke Street.