I found one solution in the Perl Cookbook using eval, alarm, and a SIGALRM handler, but I was hoping to see a better way to get this done

What's wrong with alarm?

This subroutine needs to run about 35,000 times

Sounds like some parallelism would help here. Have you considered doing multiple requests asynchronously [using Net::DNS (see the select example) or threads] to do multiple requests at the same time?