Duh! I'm being dense. Simply defer the non-CIDR attempt until the CIDR attempt fails. Right there in the callback for the first attempt we have all the information available to make the re-attempts. How does this go?

#! perl -slw
use strict;
use threads;
use Thread::Queue;
use Storable qw[ freeze thaw ];
use constant {
    ipCidrRouteProto    => "1.3.6.1.2.1.4.24.4.1.7",
    ipCidrRouteIfIndex  => "1.3.6.1.2.1.4.24.4.1.5",
    ipCidrRouteType     => "1.3.6.1.2.1.4.24.4.1.6",
    ipRouteMask         => "1.3.6.1.2.1.4.21.1.11",
    ipRouteIfIndex      => "1.3.6.1.2.1.4.21.1.2",
    ipRouteType         => "1.3.6.1.2.1.4.21.1.8",
    ipRouteNextHop      => "1.3.6.1.2.1.4.21.1.7",
    ipRouteProto        => "1.3.6.1.2.1.4.21.1.9",
};

sub warnf{ warn sprintf $_[0], @_ }

my $THREADS = $ARGV[ 0 ] || 100;

my $Q = new Thread::Queue;

## The main processing goes here
sub processResults{
    my( $host, $commstr, $result ) = @_;
    ## do your heavy stuff here
}

## simple worker thread
sub worker {
    while( my $result = $Q->dequeue ) {
        my $result = thaw $result;
        my $host = delete $result->{ _my_private_host_key };
        my $commstr = delete $result->{ _my_private_commstr_key };
        processResult( $host, $commstr, $result );
    }
}

## Callback
sub enqueue {
    ## First arg is the session handle--the rest whatever we asked for
    my( $session, $host, $commstr, try ) = @_;
    my $result = $session->var_bind_list();         ## Get the results
+ hash

#    unless( $result or $try ) ## Some people find that hard to unders
+tand.    
    if( not $result and not $try ) {
        $session->get_entries(
            -columns => [
                ipRouteNextHop,
                ipRouteIfIndex,
                ipRouteMask,
                ipRouteProto,
                ipRouteType
            ]
            ## Have host and commstr passed back to the callback
            ## Indicate this is our second attempt
            -callback => [ \&enqueue, $host, $commstr, 1 ],
        );
    }
    else {
        warnf "Failed to get_entries for $host/$commstr: reason %s\n",
            $session->error();
        $session->close;
        return;
    }
    $result->{ _my_private_host_key } = $host;      ## Tack on some ex
+tras
    $result->{ _my_private_commstr_key } = $commstr;
    $Q->enqueue( freeze $result );                  ## And serialise i
+t for queuing
    $session->close;
}

my @workers = map{
    threads->create( \&worker );
} 1 .. $THREADS;

## Avoid loading the heavy stuff until after we've spawned out threads
+;
require Net::SNMP;

open my $ipsFH, '<', 'allips.txt' or die $!;

while( my( $host, $commstr ) = split ' ', <$ipsFH> ) {
    my( $session, $error ) = Net::SNMP->session(
        -hostname => $host, -community => $commstr, -port => 161,
        -version => 'SNMPv1', -translate => 1, -debug => 0x00,
        -nonblocking => 1, -timeout => 30, -retries => 3,
    );
    unless( defined $session ) {
        warn "Couldn't create session for $host/$commstr: reason: $err
+or\n";
        next;
    }
    $session->get_entries(
        -columns => [
            ipCidrRouteIfIndex,
            ipCidrRouteProto,
            ipCidrRouteType
        ],
        ## Have host and commstr passed back to the callback
        ## first try CIDR (whatever that is?)
        -callback => [ \&enqueue, $host, $commstr, 0 ],
    );
}
close $ipsFH;

## Run the event loop
Net::SNMP->snmp_dispatcher();

## Wait for the work to be done
sleep 1 while $Q->pending;

## signal workers to die
$Q->enqueue( ( undef ) x $THREADS );

## And bury them
$_->join for @workers;
[download]