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]

Darn. Didn't think of that. Looks like you're back to one of the other two options ;(

Or, you could try NSNMP::Simple with your threaded/synchronous requests approach. A quick look at the source shows it be be pure perl and doesn't use any globals. There are a couple of lexical globals used via closure, but they should be relatively safe. The author says it's not ready for prime time, but maybe it will just work for you. Worth a shot.