Tile processing of large datasets was introduced in ArcGIS 9.2 (well, it could be done in 9.1, but it was more manual and not integrated or automatic). Even without looking at the Help, the progress window for the Union tool shows there is tiling occurring:
Maybe there were not enough qualifiers on your statement about the Union tool and new vertices because the Union tool has to add new vertices in many cases:
If your statement was meant for self unions, then I agree that new vertices seem spurious.
What steps are you using to find the extra vertices?
I am running ArcGIS 10.2.2 with all but the last couple patches, and I did find extra vertices. I only closely looked at a handful of the extra vertices, but they were all duplicate vertices. If it turns out that all of the extra vertices are duplicates, then there is no difference in the geometries of the polygons, well the perimeter and such.
The reason I asked what steps you took to find extra vertices is that I used the Feature Vertices to Points tool. Without doing more digging, I can't say whether the issue resides in the Union tool or Feature Vertices to Points tool.
Beyond the tools, have you checked how clean the polygons are? Looking at a few of the duplicate vertices, they seem to be near areas where the polygons seem to be self intersecting, or really close.