In terms of history, OpenStreetMap has been tagging more information that needed for simple vehicle navigation (as maps are used for more than just driving). At least from this OSM wiki page on footways/crosswalks Tag:highway=footway - OpenStreetMap Wiki The article history shows an earliest edit from 2012."very detailed" map is a map that have many details that are not needed for straight navigation. These details are precisely located on the map. The details could be anything from pothole, traffic control devices, crosswalks/stop lines and other road features
I would think Tesla map data partially derived from OSM had all this data, and Autopilot team figured, "well, there's all this data that we readily have available for some areas…" This could be used in vehicle for driving and visualization as well as assisting in collecting data for training.
These "very detailed" maps have been around for a long time. Whereas 3D HD lidar maps are relatively new.