Last modified: 2014-07-18 10:28:28 UTC
Doing this validation in the ChangeOp would be consistent with validation for terms and snaks. However, sitelink uniqueness is a hard constraint, actually enforced by a nunique key in the database. That may mean that it does need to be checked every time the item is saved (not just when the sitelink is modified).
To clarify: validating the value if a ChangeOpSiteLink means calling out to the API of the target wiki to see whether the respective page exists (and is not a redirect).