I do this all the time, machining both sides. I find I need to get location within a couple of tenths, usually a cosmetic problem but sometimes a functional one too. Steps in vertical walls are the most obvious flaw. A tenth is easy to see, three tenths will not be smoothed by the vibratory finishing machine and will be obvious in a finished, anodized part.
If the vise is not perfectly aligned, you will double your error when you flip the part, i.e., if one end is +0.001 in Y, then when you flip your part it will be off by 0.002 at that end.
Picking up a corner doubles you error vs. picking up something in the center. In the above example if the zero reference is in the center of the vise on both op1 and op2, you will have only 0.001 error vs. 0.002 using the corner.
Thermal stability can play a role: some C frame VMCs (maybe all?) change in Y with temperature change. Often there is a temperature change between op1 and op2, later in the day or the machine is not working as hard on one vs. the other.
I started out using an edge finder on a corner. Moved to a Blake Coax in tooling holes. Then a Haimer 3D in tooling holes. Then Renishaw electronic probes. Now my method is this:
* On first side, interpolate tooling holes (sometimes existing holes has be used) through the part blank as far left and right as possible.
* Flip, locate using one tooling hole and set datum or workshift, use second tooling hole to shift workspace rotation, aligning coordinate space with part. I use a Renishaw e-probe and programmed inline probing cycles.
* Rough second side features, leaving maybe 0.003 on perimeter features.
* Just prior to finish ops (profiling edge and round overs and chamfers), again e-probe tooling hole for position. I do not do rotation as this does not seem to drift. Position will drift for the first 2 hours or so (mostly in Y), then stabilize. Total drift from just after machine warm up to stable is about 0.0013. After lunch - or any break which idles the machine for more than 15 minutes - drifts again for an hour or two before stabilizing.
Using this method I have gotten reliable accuracy. It removes vise accuracy from the picture for the most part. Also removes edge accuracy of the blank from consideration. On small parts I do not probe for rotation, on large parts this is critical. With good soft jaws on a small part, once the machine has stabilized thermally, I do not need to probe each part for initial location. With good soft jaws, provided they have good locating features, I only need to probe the first part for rotation after first mounting the jaws except for very large parts. With good soft jaws on medium sized parts (8" lets say) I only need to probe the first part for location for roughing, but I still probe every part for location drift before finishing.