Ah very frustrating for you
It does sound like you are doing everything right which leaves me to suspect it is either down to the device (has it had an update in the last couple of months - is this causing an issue) or problems with certain books.
I have had this problem with syncing between my K3 and my iPhone which lasted for about a week and I'm still not sure whether it was just the books I was reading at the time or whether an update fixed it.
Syncing can only happen naturally with Amazon purchases that haven't been liberated so do check that the books are ones which you've downloaded from Amazon for your kindle.
The only workaround I can see right now (which is what I did) is to input the location manually when you switch device. Bit of a pain but it works. Hope your problem gets fixed.