Whilst a great answer from @pkamb. In the end my wife thought of a way to resolve this.
On the Mac (which has 7201 photos), divide this into two albums, one with 3600, and the other with 3601 Album-A and Album-B.
On iCloud check which album isn't matching, i.e. Album-A had 3601 on my Mac, but in iCloud it showed only 3600.
Repeat this process dividing the photo set in two continuously.
It took about 30 mins, but eventually I had narrowed it down to a set of photos with say 36 images. I then manually found the offending photo.
So, weirdly, it was a photo that literally didn't appear in iCloud photos. Yet when re-syncing from iCloud it would come down to a blank device. Weird.
Anyway, on my devices this innocuous photo, had a little cloud icon in the corner. again weird, not other photos had this.
I deleted it manually from both devices.
Since then all devices are in sync with the cloud, and re-syncs are working.
So there you go, strange.