[SalesForce] ContentDocumentLink insertion fails

while researching a problem similar to yours, I found an answer you might find useful:

Document already Linked

Basically the idea is to introduce a check on whether there is an existing ContentDocumentLink with the same LinkedEntityId before inserting. However, the check avoids the error but prevents insertion, which is after all not that different from your try / catch block. I still haven't found a solution to avoid the error AND insert the record. I'll keep you posted if I find it.

Rather than querying ContentDocumentId from ContentVersion, query that from ContentDocument and use that as contentlink.ContentDocumentId=documents[0].Id;

List<ContentDocument> documents = [
    SELECT Id, Title, LatestPublishedVersionId 
    FROM ContentDocument
];

ContentDocumentLink contentlink=new ContentDocumentLink();
contentlink.LinkedEntityId=availableRateDeck.id;
contentlink.ShareType= 'C';
contentlink.LinkedEntityId = availableRateDeck.Id; 
contentlink.ContentDocumentId=documents[0].Id;
contentlink.Visibility = 'AllUsers'; 
insert contentlink;

Just to let you know, following piece of code works perfectly for me

Account acct = new Account(Name='TEST_ACCT');
insert acct;

ContentVersion contentVersion = new ContentVersion(
  Title = 'Penguins',
  PathOnClient = 'Penguins.jpg',
  VersionData = Blob.valueOf('Test Content'),
  IsMajorVersion = true
);
insert contentVersion;    
List<ContentDocument> documents = [
    SELECT Id, Title, LatestPublishedVersionId 
    FROM ContentDocument
];

//create ContentDocumentLink  record 
ContentDocumentLink cdl = New ContentDocumentLink();
cdl.LinkedEntityId = acct.id;
cdl.ContentDocumentId = documents[0].Id;
cdl.shareType = 'V';
insert cdl;