This code will keep your box as long as your longest value.

my @values = qw/
                One
                Two
                Three
                Four
                Zoobdude(_Been_to_Dennys?_:)
               /;

my $longest = 0;

map { $longest = length > $longest ? length : $longest } @values;

printf "<option value='$_'>%${longest}s\n", $_ foreach @values;
[download]

Update: You wanted to use CGI.pm? Ok, this time we'll use a fixed width of 40 chars:

my @values = qw/
                One
                Two
                Three
                Four
                Zoobdude(_Been_to_Dennys?_:)
               /;

my %popup;

$popup{$_} = sprintf "%40s",$_ foreach @values;

print $cgi->popup_menu(
                       -name => 'popup',
                       '-value' => [ keys %popup ],
                       '-labels' => \%popup,
                      ),"\n";
[download]

Enjoy!

--
Casey