Radial velocities of 40 intracluster planetary nebulae (ICPNe) in the Virgo cluster were obtained with the new multi-fiber FLAMES spectrograph on UT2 at VLT. For the first time, the lambda 4959 AA line of the [OIII] doublet is seen in a large fraction (50%) of ICPNe spectra, and a large fraction of the photometric candidates with m(5007) <= 27.2 is spectroscopically confirmed. ICPNe with the velocity dispersion of the Virgo cluster are found in our CORE field 1 deg from M87. These may have originated from tidal mass loss of smaller galaxies in the M87 subcluster halo. In a field 0.25 deg from M87, we see an extended stellar halo of M87 in approximate dynamical equilibrium, but with few ICPNe. Finally, in a field near M84/M86, the ICPNe 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 non-uniform dynamical structure and on-going assembly of the Virgo cluster.(Based on data collected with the FLAMES spectrograph at the UT2 of the VLT at Cerro Paranal, Chile, operated by ESO, during observing run 71.B-0147(A))