the governments job

I do not believe that government can do something good. Of course the idea of regulation is good by itself but due to corruption and inefficiency of any government structure result will be more likely opposite (yes, I'm an anarchist and believe that only self-regulation may work).

to trace the incredibly complex chains of businesses and processes

Today it is easier than one may think: a lot of certifications and information from non-profit organization. A lot of mobile apps and sites that allow you to check how green the product is. The only missing part is request from customers side. And until we do not have such request, IMO, nothing will change.