How best to store bookmarked documents?

The fundamental principle to remember is that Scrivener can’t edit the link. It will always point to the same location, even if that location no longer works.

Bookmarks that point to a universal locator outside of Scrivener will generally survive being moved on the same computer. That includes web links, but also locators provided by some applications, such as DevonThink and Hook. (These are both Mac applications. This is the Mac forum, but your profile says you’re using Windows.) I use DevonThink a lot: they guarantee that links will work as long as the file is present in any database on the current computer. If you use this sort of link, test with the source application to see how robust it is. Whether these links will survive being moved to a different computer depends on whether the new computer has access to the referenced location and to software that created/knows how to interpret the locator.

(As a side note, the Web exists in part because of the Uniform Resource Locator, Tim Berners-Lee’s solution to this exact problem.)

Bookmarks that point to a file path or to a location inside a Scrivener project are less portable. File links will always point to the same path, even if the file is no longer there. Internal links will break if the origin or destination file is moved to another project. File links may survive being moved to a different computer, but only if the same path exists on the new system. In practice, usually that means you can buy a new computer and copy your directory structure over, but you can’t move individual files.

Yes, it’s a hard problem.