Well, I haven't read René Salm's book so I can't give my opinion on what he says (although I know that at least one archaeologist was quite critical of it in peer review). I am somewhat more circumspect on the subject than Randi, who regards the matter as conclusively proven. On the one hand, there is no external evidence of a Galilean town named Nazareth until the third century AD, and thus is not among the 45 Galilean towns and villages mentioned by Josephus and the 63 Galilean towns and villages named in the Talmud. Archaeological evidence of Roman-era occupation at modern Nazareth has also been slight, depending on how it is interpreted. However since literary references were not exhaustive and were motivated by authorial concerns (Josephus mainly mentions places that figured in the AD 66-70 Jewish revolt and the Talmud is concerned with locations of rabbinical schools and rabbi hometowns), the absence of Nazareth is suggestive but not necessarily conclusive. The apparent lack of archaeological evidence depends, among other things, on where one digs and whether biblical Nazareth even corresponds to modern an-Nasira. The absence of evidence on both counts may be expected if Nazareth was a very small village or hamlet.
What makes me take the possible existence of Nazareth more seriously is the evidence that some place in Galilee bore that name in the third century AD and the unliklihood that it was named by Christians influenced by the gospel use the place name. Julius Africanus (writing c. AD 221) described a "village" named Nazara, a Caesarean Hebrew inscription from c. AD 275-325 refers to a priestly family having settled in Ntsrt since the Bar Kosiba revolt (a similar reference is found in a much later poem by Eleazar Kalir), and Epiphanius around the time of Constantine also mentions the town of Nazareth having only recently been settled by Christians (Panarion 1.30.11). The inscription shows that it was inhabited by a prominent Jewish family since around the middle of the second century AD and the report by Epiphanius observes that it had only Jewish inhabitants. If no such place bore the name "Nazareth" in the first century at the time the gospels were written, then how did just such a place arise a century later with that name, which looks very much like a non-Christian Jewish community (who thus wouldn't take the name from the gospels)? The names attested in the gospels, Nazara, Nazaret, and Nazareth, also are not derived from Nazóraios "Nazorean", as may be expected if the name of the town is a back-formation of "Nazorean" (i.e. the name is never spelled "Nazoret" or "Nazoreth"). The multiplicity of spellings is also suggestive of an actual name that has been transliterated differently from Semitic (the feminine ending being variably retained; it was commonly retained in Galilee under influence from Phoenician). There is also an interesting pattern in the attestation of Nazar- names in the NT. Mark, the oldest gospel, uses only Nazaret and the gentilic Nazarénos "Nazarene"; the term Nazorean is never used. The latinized form Nazarénos is quite normal for Mark and explicable from Nazaret. Matthew, Acts, John however never use this form and exclusively use Nazóraios "Nazorean" (while Luke uses both). This suggests that at the earliest stage, the names "Nazareth" and "Nazarene" had nothing to do with the Nazoreans (and indeed Epiphanius makes a distinction between the Nazaraioi and the Nazóraioi, and there are indications that the Nazóraioi were a pre-Christian group), but at a later stage (when Mark was revised by Matthew and when John was composed) the originally distinct names were conflated, probably on account of the self-identification of certain Jewish-Christians as Nazoreans. The exegetical move in Matthew 2:23 is one attempt to force such a link, making the name Nazóraios derivative of Nazaret (even though it is not, we would rather expect Nazaretaios or Nazareténos). The form Nazara meanwhile is only found in the double tradition materal (i.e. at Matthew 4:13 and Luke 4:16), and on the Q hypothesis woud be explained as the spelling used in the Q sayings source, as opposed to the different spelling found in Mark.
So while "Nazorean" was the name of a sect or religious group (as it is in Acts 24:5), "Nazarene" imo originally signified a person from Nazara/Nazaret. And while the origin of "Nazorean" is unclear, it may well derive from nzr "abstain" (whence nzyr "Nazirite", in this case it would be nzwry), and the author of Matthew probably relates it to this word if the intertext involved is Judges 13:5, 7 (which has Naziraion in LXX-A). "Nazareth" and "Nazarene" on the other hand derive from an entirely different root, either ntsr (netser) "shoot, branch" or ntsr (nastar) "watch, guard, keep". The latter is more fitting for the name of a town or lookout although the former root has messianic resonance on account of Isaiah 11:1. What is important in either case is that ntsr is entirely different from nzr in Hebrew and the two could only be confused in Greek (which commonly renders both tsade and zayin with the letter zeta), which of course is the language that Matthew was written in. Yet the later Hebrew term for Christians was Notsri (nwtsry), which clearly derives from ntsr and not nzr. So whatever the sense of "Nazarene" in Mark, it may have continued on as a Christian self-label, influenced by the messianic connotations of Isaiah 11:1; thus the author of Luke treats "Nazorean" and "Nazarene" as interchangeable, as he keeps the Markan "Nazarene" unchanged in Luke 4:34 (= Mark 1:24) and uses it innovatively in 24:14, whereas he changes the Markan "Nazorean" to "Nazarene" in 18:37 (= Mark 10:47).
But who knows, it's a complex puzzle and no one probably has it all solved yet.