Most stuff actually is fairly well recorded "somewhere". No work gets done without getting locates before (yellow, orrange, blue lines etc), that are generated by surveyors based on both as-built plans, and confirmed on-site from geophysical investigation instruments, be it metal detercors or ground penetrating radar etc.
After something is installed you have to provide detailed plans of location depth etc. usually in the form of drawings (both plan and profile for line structurese such as utility pipes or cables). Tables with coordinates and elevations may be sufficient for more compact objects. And you have to do a survey for the as-builts, the original plans are not good enough for final submission. (That is for any project of any magnitude that will require city approval... what people do in their backyard won't be covered).
What often happens is that (as in this case) something is there, and reported the site investigation report, but its presence goes unnoticed in the volume of data looked through when working on the project. Or it was noted originally, but the alignment of the tunnel was different and it was not a concern, but a last minute change in alignment makes it a concern and people (being people) just forget there was somthing there to consider, because they HAD checked those things before after all, and already figured out there was no concern.
Of course, whent thing are very old, the problem is often getting access to the documentation. Either it was done in a time when records were not kept as thoroughly, or the they are just very hard to track down for one reason or another. Usually, if something does require city approval though, you can find those submissions... and as long as nobody bribed a city inspetor to look the other way while corners were cut , they should provide a reasonable estimate of where things are. The main difficulty is actually tracking down all activities that may have been undertaken at that location over time. While the record may exist, making sure that all things that were done (as owners changed over time) are considered may be challenging depending on the data tracking and storage implemented at the city level over time.