Charlie - those things didn't help - tried both ELIMINATE and CHECK/REPAIR GEOMETRY.
But it did work in Workstation, using this workflow:
* Export to coverage from within ArcMap
* BUILD [coverage] arc
* In ArcEdit, one does an 'aselect' on arc with lpoly#/rpoly# = 1 (universe polygon)
* put [new coverage]
And that's it!
Hugo was kind enough to send me his data and I reproduced the problem and didn't figure it out immediately, so I passed it along to the guys on the geoprocessing team.
So the problem was similar to what I originally thought--the vertexes in the original data do not quite coincide. On the Poland USSR border some were literally only a couple of millimeters apart. I was zooming in, but not far enough. I'm guessing the guys on the geoprocessing team converted the FEATURE VERTICES TO POINT and then verified the coordinates.
My regret is forgetting the name of, and entirely about, the command that fixes that. In Desktop we have a tool called INTEGRATE. I processed Hugo's features with a 5m tolerance and then ran POLYGON TO LINE and it worked like a champ.
So, there really isn't a need to go back to Workstation for that issue.