First post, also having this issue.
I think the problem is in iCloud sync jobs. I believe their queue is completely out of control that is why the jobs are processed by delay. FWIW, I called the missus with FaceTime and she got the call after a few minutes, after I had hung up...
Considering its a problem with the scheduled jobs in iCloud in general, I don't know how they could fix it. I assume they could just clear the whole queue but that would cause issues too, also now they are trying to do conflict resolution I guess which adds a cherry on top. Moreover, that would not fix the root cause, most likely.
All in all, I wonder when they will fix this issue. If you want to dig little bit deeper, enable the 'Debug' menu in Safari, with:
defaults write com.apple.Safari IncludeInternalDebugMenu 1
Now you can force sync 'iCloud History' however it will just push it to the queue... I would really appreciate Apple to be more transparent with these issues as this bug has really messed up my workflow and I can't do anything about it.