Out Of Copyright Maps
Seeing that the OSM maps need to be created from either collected GPS traces or out of copyright maps (specifically to get the street names), I've included a few links or actual images that I've collected
The State Library of Victoria has digitised the majority of the Melbourne Metropolitan Board of Works (MMBW) maps that date from the late 1890's through to the 1950's. For maps that are up to 100 years old, they are surprisingly accurate - I've found a handful of streets that have changed names, and obviously heaps of streets that no longer exist, but these maps are an excellent start when tracking down street names (and are interesting from an historical viewpoint as well). THe MMBW map catalog can be accessed from the MMBW Melbourne Sewerage Plans website.
I spent some time in the State Library recently determining the copyright state of the MMBW maps above (which are fine to use as a map source for street names), and located a 1936 Collins street directory. Seeing as you are now allowed to use digital cameras in the State Library, I photographed the entire directory. Go here for the complete list of all 128 images
Cameron kindly provided these maps for all and sundry, photocopied in the State Library in South Australia. It seems that the SA State Library isn't as liberal with their allowing of digital cameras into the hallowed halls, so these are all high quality photocopies (which are basically better quality than my digital snaps above). Go here for the complete list of all 48 images