which means that the hash %alt_seqindex is the one I end up doing most of my searches on. It seems that building this second hash takes a very long time

Thats because Hash::Case::Preserve does everything in memory.

Here's what I'd do (assumes your keys don't end in "_\0_key")

package BerkeleyDB::Hash::CasePreserve;

use BerkeleyDB;
use base qw[ BerkeleyDB::Hash ];

sub FETCH { $_[0]->SUPER::FETCH( lc $_[1] ) }
sub EXISTS { $_[0]->SUPER::EXISTS( lc $_[1] ) }
sub NEXTKEY {
    my $next = "";
    do {
        $next = $_[0]->SUPER::NEXT($_[1]);
    } until
        0 < index
               $next,
               "_\0_key",
                - length "_\0_key";

    return $_[0]->SUPER::FETCH( $next ); # oRiGiNal cAsE
}

sub STORE {
    $_[0]->SUPER::STORE(
        lc($_[1])."_\0_key",
        $_[1],
    ); # oRiGiNaL cAsE

    return $_[0]->SUPER::STORE( $_[1], $_[2] );
}
[download]

This has the benefit of being self contained and memory efficient.