How to get a list of all possible values of a specific user meta key?

Perhaps you could create a private utility taxonomy bookmarks, where each term would correspond to a user. When ever a user is created a new term would be added to the utility taxonomy. As the user bookmarks or removes one’s bookmark from a post, your code would attach or detach the user equivalent term from the post.

The user ID could be saved as the term name and/or slug, which you could use to do “reverse lookups” e.g. turn the term name into a integer and query single user with it.

To find out who has bookmarked a post, you’d simply use get_the_terms($post_id, 'bookmarks'), turn the term names to an array of IDs, and query the users with WP_User_Query(array('include' => $user_ids)).