I'm not sure about the CGI part of it, but for the actual checking of the link you might want to look into LWP::UserAgent and for an example of LWP::UserAgent in action, try looking here. It's a long script, but maybe it'll give you some ideas.

You may just want to let the server handle 404 errors on your side. If it's their server with the bad link, just validate your links every so often with a cron job and have somebody look over the results every so often to take out links that are permanently down. Checking every link as you click it would waste system resources and slow down your site more than necessary.