I haven't read all the way through this one yet, but... 1st point, when I started working in horizontal/linear construction, we often were only working around 1 phone/fiber, 1 cable, maybe a water, gas and sewer. Now, most road right of ways will have 5 or 6 fiber companies (Uniti, crown castle, lumin, att, Comcast, Vero, MCI, Windstream, Cox, ect). There is one particular, semi rural roadway i work on a lot, we have 2 gas mains (different companies), 13 telecoms, water, sewer, some buried power, and a high profile ATT transmission, that allegedly connects North America to South America.
2nd point, 10-15 years ago, the answer was always, Just go deeper to get under everything. In the past decade we have put gas as deep as 105 feet (36" steel line going to a power plant), and fiber as deep as 45 ft, and many water/forcemain/reclaimed water/gas in the 30-60 ft deep range. We are rapidly running out of "deeper".
3rd point, the UAOs (Utility Agency Owners), don't do sufficient oversight and mapping of what their contractors install, so they don't have good maps to give their 3rd party locators.
4th point; locating has improved, but not by leeps and bounds. GPR helps, but its really got it's limits. Tracer wires get cut and not repaired, ect.
5th point, not everything buried is a "utility", stuff like signals, ITS, street lighting, storm drains, ect are exempt from having to be located