The specification was called XDS and was developed by Sony to automatically set the clocks on their VCRs. PBS was a major participant but some other networks included XDS timecodes as well. Unfortunately late in the systems life reliability became poor (the encoder was not integrated with any of the other station equipment and was not being modernized) and I assume they all died out with the digital transition.
A better source today would be the time codes sent out by some FM radio stations with RDS encoders, to allow car radios to set their clocks. Unfortunately not that many radio stations do this and, once again, the time is not always all that reliable since the RDS encoder may not have any synchronization source itself.
The cellular network used to be an excellent source, CDMA cells required GPS time sync for TDMA reasons (well, CDMA reasons, technically speaking...) and broadcast a time code that is directly off of their GPS time source. Unfortunately, while GSM cells (and LTE) do broadcast the time, there is no guarantee made of precise synchronization as they don't broadcast a time code directly from their GPS source (not an expert in this field but I think the GSM/LTE time information comes from the possibly remote controller rather than the local radio hardware). Still, it would probably be good enough for this application.
GPS time sync is actually quite cheap to implement these days but tends not to work in these scenarios since a clear sky view is needed. WWVB is possibly on the way out. SNTP is probably ruled out less by the BOM cost of WiFi hardware and more by the deployment pain of having to get kitchen equipment configured for the corporate WiFi network.
Here's a fun idea: McDonalds presumably centrally controls the in-restaurant audio. Could they encode timestamps into the background music in a way that machines can cheaply recover? You wouldn't need high reliability, just enough for it to work once in a while. The old-ish Nielsen Peoplemeter system would be a model.