Which happens with "visited stars" already.
It'd be a file that you could save and replace.
And we already have players who complain because they have lost their "visited stars" list and why can't FDEV just give it back to them because they know where they have been!
I can imagine players re-installing and not knowing that bookmarks are locally stored and complaining that all their valuable bookmarks have vanished. I guess that's a good argument for sidewinder markers for stations, at least they wouldn't vanish on re-install.
Personally I would suggest 2 systems, I would be quite happy with locally stored personal bookmarks and server stored shared or otherwise "important" bookmarks. Actually just thinking it could be done quite easily if bookmarks were made part of the journal output, that way programs like EDDiscovery could rebuild your bookmark list for you, but of course that would still require players to back up their journal files so there's still some player action required, and I can tell you having worked in IT for ten years, that's not going to happen in a lot of cases!