Radial velocities of 40 intracluster planetary nebulae (ICPNs) in the Virgo Cluster were obtained with the new multifiber FLAMES spectrograph on UT2 at the Very Large Telescope. For the first time, the λ4959 line of the [O III] doublet is seen in a large fraction (50%) of ICPNs spectra, and a large fraction of the photometric candidates with m(5007)<~27.2 is spectroscopically confirmed. ICPNs with the velocity dispersion of the Virgo Cluster are found in our CORE field 1.2d from M87. These may have originated from tidal mass loss of smaller galaxies in the M87 subcluster halo. In a field 0.25d from M87, we see an extended stellar halo of M87 in approximate dynamical equilibrium but with few ICPNs. Finally, in a field near M84/M86, the ICPN velocities are highly correlated with the galaxy velocities, showing that any well-mixed intracluster population is yet to form. Overall, the measured velocity distributions confirm the nonuniform dynamical structure and ongoing assembly of the Virgo Cluster. Based on data collected with the FLAMES spectrograph at the UT2 of the Very Large Telescope at Cerro Paranal, Chile, operated by ESO, during observing run 71.B-0147(A).