Two ideas for ya':
1) Make the GIF banner be printed with a PHP script. (My signature graphic below is an example. It's generated by a PHP script.)
Each person that enters information for your link referral program should have an associated name (link name, perhaps). The code you give them should be http://your-site.com...heir_link_name.
With that PHP script (graphic.php), keep a list of those link names that have requested the image (like in linknames.txt). That proves that they have the image in their HTML.
On your links page, check each link name against linknames.txt. If it's not there, don't display their link.
2) PHP could fetch each page and find the URL to your gif file in their HTML. Note: Fetching external websites and verifying an image to be in their HTML code in real-time takes quite a bit of time.
P.S. Does this make any sense to you? It makes sense in my mind, at least.