If you have sync, and there is a problem anywhere, Shut Down Sync Immediately On All Devices to prevent the problem from spreading. Once the problem is fixed, perform the same repair on all computers/profiles before using sync again.

[v57+] Places Maintenance is built into Firefox.

Type about:support<enter> in the address bar.

You will find Places Database near the bottom. Press the Verify Integrity button.

When done, copy and post the results here.

https://support.mozilla.org/en-US/kb/fix-bookmarks-and-history-will-not-be-functional

I'm not syncing anything besides bookmarks and addons (and those are verified to not cause the issue, same set on my wife's PC and all is fine there) and only on one machine, so it doesn't have anywhere to spread.

Integrity log: https://pastebin.com/3EAJdQpA

Did you run the Places Maintenance as suggested?

Probably minor corruption that Maintenance will fix.

Plus, Sync isn't intended to be used with a solitary device. Best to properly backup your Firefox Profile to an external medium, like USB Flash Drive. Many users have lost their data by using Sync with one device, without having a real backup. IMO, the method of encryption is too high; simply resetting the Firefox Account password which is used to for encryption of user data when it is off each individual device will result in Sync data to be cleared from the Sync server. A new password would create a new encryption key making any data in the Sync system a worthless 'blob'.

I did run integrity verification, not sure if there's anything else that I missed. So far though testng with few random bookmarks seems the issue is gone, so there's that =) I do have a backup of my profile, updated every other week or so. Sync is just more convenient to me =)

As the-edmeister said, Sync isn't intended to be used as a backup
It's too easy to lose the very data you want to save.

Back up and restore information in Firefox profiles {web link}
I use an add-on that makes backups of my user profile, Just In Case.
Unfortunately, it is not compatible with the current Firefox.

Every now and then, open the profile folder and create a copy of the current profile as is to another location on your hard drive. This way you will have a backup.

If you do this each day, you will not lose much data. This should be done with Firefox Closed.

Note: In case you need to restore from these backups, you may need to overwrite old or corrupted files.