The cause has been found with a call server which had lost its time on a reboot and did not automatically sync back with NTP.
This resulted in around 30% of calls receiving the message depending if they hit this call server.
The time process has been set and issue resolved.