Je pense que le meilleur moyen serais que le tiers mettent un code Javascript qui vérifie la présence sur la page du lien avec une id particulière et te renverrais un résultat sur ton serveur "Ok le lien est présent".
Ou alors tu fais une tâche cron que tu executes tout les jours dans la nuit avec un script php qui va crawler tout les sites des tiers pour vérifier la présence de ton lien et t'enregistrer si oui ou non à tel heure il y figurais.
Je faisais un appel curl sur une certaine url "Serveur de jeu qui me sortais du HTML directement" et je pouvais récupérer le dom grâce à:
http://simplehtmldom.sourceforge.net/
Je pense que simplehtmldom va grandement t'aider, c'est un peu chiant à débugger mais une fois mis en place ça marche niquel