iCloud: Troubleshooting Safari bookmarks sync between Windows and OS X
I diagnosed and fixed my sync problem. It's been three or four days of bookmarks syncing without any hiccups.

Narrowing the scope

The original problem was so tough because I had no simple way to find it whether the Mac Safari, or Windows Safari, or both, failed to sync.

To find out if the iCloud on Windows works, do this:


Change the Sync bookmarks with option in iCloud to Internet Explorer, wait a bit (sadly, iCloud doesn't seem to display any kind of sync progress anywhere).
Open Internet Explorer, add a bookmark or two, wait to give iCloud a chance to sync.
Change the Sync bookmarks with option in iCloud to Safari, again, wait.
Open Safari, check if the bookmarks added in Internet Explorer are there.
Add another couple of bookmarks in Safari, wait.
Change the Sync bookmarks with option in iCloud back to Internet Explorer, wait.
Open Internet Explorer, check if the bookmarks added in Safari are there.


Now, in my case, all worked OK on the Windows iCloud part, so next thing I had to do was diagnosing the Mac part.

Fixing the problem

Apple KB article iCloud: Troubleshooting iCloud Bookmarks was an excellent source of help, once I knew which part of the setup to fix.

The steps that actually helped me in my Mac Safari problem case were these (see Troubleshooting iCloud Bookmarks update/setup issues on OS X Lion):


  
  Quit Safari.
  Choose System Preferences from the Apple () menu and then choose iCloud.
  Remove the checkmark in the checkbox next to Bookmarks.
  Close System Preferences and wait about a minute.
  Open System Preferences and choose iCloud
  Replace the checkmark next to Bookmarks.
  Close System Preferences.
  Open Safari and test to see if the issue has been resolved.
  


For Windows iCloud problems, there's a separate section,
Troubleshooting iCloud Bookmarks update/setup issues on Microsoft Windows, which probably should be helpful as well.