Cell search is the process for a user to detect its neighboring base stations (BSs) and make a cell selection decision. Due to the importance of beamforming gain in millimeter wave (mmWave) and massive MIMO cellular networks, the directional cell search delay performance is investigated. A cellular network with fixed BS and user locations is considered, so that strong temporal correlations exist for the SINR experienced at each BS and user. For Poisson cellular networks with Rayleigh fading channels, a closed-form expression for the spatially averaged mean cell search delay of all users is derived. This mean cell search delay for a noise-limited network (e.g., mmWave network) is proved to be infinite whenever the non-line-of-sight (NLOS) path loss exponent is larger than 2. For interference-limited networks, a phase transition for the mean cell search delay is shown to exist in terms of the number of BS antennas/beams $M$: the mean cell search delay is infinite when $M$ is smaller than a threshold and finite otherwise. Beam-sweeping is also demonstrated to be effective in decreasing the cell search delay, especially for the cell edge users.