Think I found the cause. On one of the problem lists the workflows were set to auto-start and kick off on item creation and modification.
It’s the recursive nature of the Workflows that's recording the message in workflow history. Found the following errors in ULS logs:
WinWF Internal Error, terminating workflow Id# 3dd2a077-449a-418d-91d3-5cc2b5a709bc
AutoStart Workflow: Microsoft.SharePoint.SPException: Recursive workflows are not permitted. at Microsoft.SharePoint.Workflow.SPWorkflowAutostartEventReceiver.<>c__DisplayClass1.b__0(SPSite superUserSite, SPWeb superUserWeb)
Recursive workflows can overload SharePoint timer service and that’s why it records that message as an FYI.
As suggested in the forums here we need to either modify the workflow design or add a pause action and see check:
Start workflow automatically
https://social.msdn.microsoft.com/Forums/en-US/81b405bd-cbdd-4a4d-8e8b-67e5134d3ccb/autostart-workflow-microsoftsharepointspexception-recursive-workflows-are-not-permitted?forum=sharepointcustomizationprevious
One thing that's still puzzling me is why did we not see the same issue in SP2013 farm. This seems to have started only after migrating to SP2016.