Problem with Sync bookmarks across devices

Description of the issue:
New bookmarks does not propagate to other devices (not even after 24 hours).
I even tried to remove one device (Android) and added again by reading QR code, but still the same problem.

Steps to Reproduce (add as many as necessary): 1. 2. 3.
Adding new bookmark and wait not to be propagated to other devices.

Reproduces how often:
9 out of 10 new bookmarks? I can say for sure that most new bookmarks does not propagate.

Brave Versions:

Type of devices currently running on the Sync chain in question:
2 windows, 1 Linux and 1 Android

Additional Information: