Should the parallels be able to slide in and out when the vise is tightened?

No. If parallels move around or completely slide out of the vise, the part has fewer contact points keeping it stationary and elevated above the surface of the vise. This shifting then messes up your milling operations. You may wish to lightly tap down the parallels using a soft blow mallet to ensure that they are fixed in place. See here.