The phase velocity dispersion of longitudinal waves in polycrystals with elongated grains of arbitrary crystallographic symmetry is studied in all frequency ranges by the theoretical second-order approximation (SOA) and numerical three-dimensional finite element (FE) models. The SOA and FE models are found to be in excellent agreement for three studied polycrystals: cubic Al, Inconel, and a triclinic material system. A simple Born approximation for the velocity, not containing the Cauchy integrals, and the explicit analytical quasi-static velocity limit (Rayleigh asymptote) are derived. As confirmed by the FE simulations, the velocity limit provides an accurate velocity estimate in the low-frequency regime where the phase velocity is nearly constant on frequency; however, it exhibits dependence on the propagation angle. As frequency increases, the phase velocity increases towards the stochastic regime and then, with further frequency increase, behaves differently depending on the propagation direction. It remains nearly constant for the wave propagation in the direction of the smaller ellipsoidal grain radius and decreases in the grain elongation direction. In the Rayleigh and stochastic frequency regimes, the directional velocity change shows proportionalities to the two elastic scattering factors even for the polycrystal with the triclinic grain symmetry.