We present inelastic neutron scattering data across the Verwey transition in magnetite, obtained for a single crystal via a detwinning method. We provide direct evidence of the influence of the charge order on the transverse-acoustic phonons, associated with discontinuous hardening and narrowing at the transition temperature, and energy splitting for different polarizations. This contrasts with the behavior of the transverse-optical X3 mode, which does not present any critical anomaly, contrary to theoretical expectations. Our data indicate that the incommensurate fluctuations occurring above the critical temperature become locked to the lattice at the transition point, through a mechanism similar to the crystallization of a two-dimensional liquid on a solid surface. Our results also contribute to clarify the different dynamics and mutual interactions of the electronic and structural modes in the Verwey transition.