Like Hans, I am a big fan of digitizing in AI with MAPublisher, having used this approach to create most of Natural Earth's foundational vectors. Digitizing with the pen tool and Bézier curves, converting the Béziers to short straight line segments, and exporting them as shapefiles works efficiently. Handing off data between MAPublisher and Arc—we do this with Natural Earth—is not a problem, so multiple folks on different platforms could contribute.
If this project is undertaken, including historical boundaries as part of the Natural Earth dataset is worth considering. In Natural Earth, if you delete the modern reservoirs there are river centerlines below, approximating river alignments prior to the twentieth century. Natural Earth also contains former coastlines of the Aral Sea and Lake Chad.
I'll ping Nathaniel about this.