The last question is, do I have to create a new LinkItemCollection with updated values and add this to the current page?

Does it work if you run it manually (as admin). Scheduled job normally runs as anonymous user if you haven't done anything when running automatically so that is a possible issue if you get any errors?

If that's the case use 

PrincipalInfo.CurrentPrincipal = PrincipalInfo.CreatePrincipal("your.username");

To let the job run as your.username...

Also check that you are actually publishing page and not just saving it. Use 

ContentRepository.Save(clone, SaveAction.Publish);

Or similar...

Do you get any errors in log?

Hi yes the job is elevated as Administrator.

if (HttpContext.Current == null)
{
PrincipalInfo.CurrentPrincipal = new GenericPrincipal(
new GenericIdentity("Scheduled Job - UpdateLinkItemCollection"),
new[] { "Administrators" });
}

SaveAction:

contentRepository.Save(writableClone, EPiServer.DataAccess.SaveAction.Publish, EPiServer.Security.AccessLevel.NoAccess);

No errors in EPiServer

Tried remove the link and then save it? If that works the simply add the new link after removing the bad one. 

If not, try clone the link collection first and do the same procedure as work around...Might be that episerver fails to detect the change deep within an existing property since the object reference to the link collection will stay the same. DotPeek will know  :)

Have you debugged the code and actually seen that it goes in and finds the match? Don't know if this will be any better, but you can try to cast the value of the property to LinkItemCollection (writableClone.Property[i].Value as LinkItemCollection) and foreach throught that.. Or maybe try to foreach propertyLinkCollection.Links instead? Just a shot in the dark here without actually trying it out :)

Tim yes I log the exact match when iterating the Linkcollection.

Daniel I think the best approach is to clone the collection and when all LinkItems is handled I republish page with the new updated clone.

I think that will work yes Christer. Let me know if it works out :)

Thanks Tim, you are right

It only works if you access it like (writableClone.Property[i].Value as LinkItemCollection) and changing each LinkItem has effect and it updates database.
All other options do not updated values, and they remain the same.

Without actually testing myself I would guess that the issue is that the property itself is not marked as modified when an item in the collection is changed (it is probably just tracking add/delete not modify of an individual item). If so setting property.IsModified = true should make it persisted.