In millimeter-wave wireless networks, the use of narrow beams, required to compensate for the severe path-loss, complicates the cell-discovery and initial access. In this paper, we investigate the feasibility of random beam forming and enhanced exhaustive search for cell-discovery by analyzing the latency and detection failure probability in the control-plane and the user throughput in the data-plane. We show that, under realistic propagation model and antenna patterns, both approaches are suitable for 3GPP New Radio cellular networks. The performance gain, compared to the heavily used exhaustive and iterative search schemes, is more prominent in dense networks and large antenna regimes and can be further improved by optimizing the beam forming code-books.