Triggers can fire on ContentVersion when new ContentDocuments are created or updated. See my answer to Trigger on ContentDocument not working for more on this. It appears to me, based on what I've italicized below, that you need to be querying by getting the ContentDocumentId from the ContentVersion Object instead of the ContentDocument Object, especially since I'm guessing you're likely looking for a version of the document. Everything below is taken from the Object Reference.
The following is said about ContentDocumentLink:
Use this object to query the locations where a file is shared or query which files are linked to a particular location. For example,
the following query returns a particular document shared with a Chatter group:
SELECT ContentDocument.title FROM ContentDocumentLink WHERE ContentDocumentId =
'069D00000000so2' AND LinkedEntityId = '0D5000000089123'
• You can't run a query without filters against ContentDocumentLink.
• You can't filter on ContentDocument fields if you're filtering by ContentDocumentId. You can only filter on
ContentDocument fields if you're filtering by LinkedEntityId.
• You can't filter on the related object fields. For example, you can't filter on the properties of the account to which a file is
linked. You can filter on the properties of the file, such as the title field.
A SOQL query must filter on one of Id, ContentDocumentId, or LinkedEntityId.
Edit - More on ContentDocumentLink:
Special Access Rules
• Customer and Partner Portal users must have the “View Content in Portal” permission to query content in libraries where
they have access.
• Users (including users with the “View All Data” permission) can only query files they have access to, including:
◊ All Salesforce CRM Content files in libraries they're a member of and in their personal library, regardless of library
permissions (API version 17.0 and later).
◊ All Chatter files they own, posted on their profile, posted on groups they can see, and shared directly with them (API
version 21.0 and later).
• For API version 25.0 and later, creation and deletion of ContentDocumentLink objects with a LinkedEntityId of types
User, CollaborationGroup, or Organization are supported via the API.
• For organizations with the Communities pilot enabled, a document can only be shared with users and groups that are a
part of the community the file was created in.
Here's some of what you'll find under ContentVersion:
• Use this object to create, query, retrieve, search, edit, and update a specific version of a Salesforce CRM Content document
or Chatter file. Use the ContentDocument object to retrieve, query, update, and delete the latest version of a document,
but not a content pack, in a library or a file in Chatter.
• Use this object to create, query, retrieve, search, edit, and update a specific version of a Chatter file. Use the
ContentDocument object to retrieve, query, update, and delete the latest version of a file in Chatter.
• If Chatter isn't enabled, Chatter files aren't included in query results.
• You can't query files that are only on records, whether they're public or not.
• Not all fields can be set for Chatter files.
• You can only update a version if it is the latest version and if it is published.
• You can't delete a version via the API.
• SOQL queries on the ContentVersion object return all versions of the document. SOSL searches on the ContentVersion
object return only the most recent version of the document.
• Documents published into a personal library assume the default (General) content type.
Note: When Salesforce CRM Content is provisioned for an organization the administrator can create a General
content type. Additional content types can be created to categorize documents. The administrator can rename
the General content type.
And this is what's said about ContentDocument:
• Use this object to retrieve, query, update, and delete the latest version of a document, but not a content pack, in a library
or a file in Chatter. Use the ContentVersion object to create, query, retrieve, search, edit, and update a specific version of
a Salesforce CRM Content document or Chatter file.
• The query() call doesn’t return archived documents. The queryAll() call returns archived documents.
• If Chatter isn't enabled, Chatter files aren't included in query results.
• You can't query files that are only on records, whether they're public or not.
• To create a document, create a new version via the ContentVersion object without setting the ContentDocumentId.
This automatically creates a parent document record. When adding a new version of the document, you must specify an
existing ContentDocumentId which initiates the revision process for the document. When the latest version is published,
the title, owner, and publish status fields are updated in the document.
• When you delete a document, all versions of that document are deleted, including ratings, comments, and tags.
• You can't create, edit, or delete content packs via the API.
Note: Content metadata, such as tags, custom fields, and content owners are tracked at the version level rather
than at the document level.
• If you query versions in the API, versions with a PublishStatus of Upload Interrupted are not returned.
• A document record is a container for multiple version records. You create a new version to add a document to the system.
The new version contains the actual file data which allows the document to have multiple versions. The version stores the
body of the uploaded document.
Edit - Content Objects Schema:
Edit - User Sharing Permissions Schema:
Edit - In the Object Reference, under PermissionSet, I found the following and more:
Child Objects
When using the API, think of each permission set or related set of access controls as starting as an empty container that you
fill with permission records.
In the API, a permission set can contain user, object, and field permissions, as well as setup entity access settings for other
settings, such as Apex classes.
• ObjectPermissions and FieldPermissions objects are available in API version 24.0 and later.
• The SetupEntityAccess object is available in API version 25.0 and later.
Only user permissions are managed in the PermissionSet API object; all other permission types are managed in child API
objects.
In these child objects, access is stored in a record, while the absence of a record indicates no access. In order to return a record
in a SOQL query, a minimum permission or setting is required for each child object.
Because permissions are stored in related objects, it’s important to understand what questions to ask when using SOQL. For
example, you may want to know which permission sets have “Delete” on an object or have the right to approve a return
merchandise authorization (where the approval checkbox is controlled with field permissions). Asking the right questions
when using SOQL with permission sets will ensure that you get the information you need to make an informed decision, such
as whether to migrate permissions or assign a permission set to a user.
To set an object or field permission to no access, just delete the record that contains the permission. For example, to disable
all object permissions in the Merchandise__c object for a particular permission set, first query to retrieve the ID of the object
permission record.
SELECT Id
FROM ObjectPermissions
WHERE SobjectType = 'Merchandise__c'
Then delete the IDs returned from the query.
Note: If you try to update the object or field permissions by setting all permissions to false, the permission record is
automatically deleted. As a result, any subsequent queries for the record ID won’t return any results and you must
add a new permission record to grant access.
Edit: Final Comments
The above note confirms your observation that record IDs are lost when once a document has been unshared. ContentDocumentLink only has 4 fields that aren't standard System Fields. Those fields tell very little and are mostly picklists. It appears to me that the ContentDocumentLink is going to tell you very little in terms of sharing.
If detecting changes in sharing is your primary objective, I recommend you study the example queries in PermissionSets section of the Object Reference Document to gain further insight into how to achieve your desired results. There were too many query examples for me to cite them all in this answer.
It's my sense that your solution will likely include some combination of Permission Sets, Document Libraries, Sharing Groups and ContentVersion/ContentDocument. I hope what I've provided helps provide some clarity for you.
