Big part of my problem was leaving some labels that interfered with labels created for export. Then, after importing, things did not fall correctly in place.
I corrected this, but I think still there are cases of broken threads, but so few I am not going to investigate it further. Maybe message ids are not correct after all.
Discovered the same thing as @xyzzy today. This is from a brand new sync account created yesterday! Come on Opera, at least let us know if there is some kind of work around for this annoying broken sync feature. At least introduce some kind of tool (as @raaimin2 suggested) that makes it easy to remove duplicates.
Even a temporary Fix would be a remove duplicate button. This would rapidly reduce the need for the user to manually go through their bookmarks and even with the fix would still be a nice feature to have in case its a user error instead of the a technical one.
The dev team doesn't hang out here so requests like this are only heard by your fellow users. That said, have a look at this: http://blogs.opera.com/desktop/2015/03/sidebar-extensions-speed-dial-syncing-customizable-shortcuts-opera-developer-29/ Its not exactly what you are looking for but its proof that Opera is going that way.