and probably a tiny bit faster

Yep, you've got me there, and then some:

           Rate      OP   other  fishbot   Joost
OP        293/s      --    -21%     -76%    -92%
other     369/s     26%      --     -69%    -90%
fishbot  1205/s    312%    226%       --    -68%
Joost    3723/s   1173%    908%     209%      --
[download]

"other" was a solution using values with a regex. "OP" was a corrected key and regex version of the OP's code.

Update: Added OP-style solution to benchmark.

use strict;
use warnings;

use Benchmark qw{ cmpthese };

our %a;
$a{ $_ } = "foo" for 1..1000;
$a{ 1 + int rand 1000 } = '' for 1..10;

cmpthese( -3,
   {
      Joost    => 'scalar grep { $_ ne "" } values %a',
      fishbot  => 'scalar grep { $a{$_} ne "" } keys %a',
      other    => 'scalar grep { ! /^$/ } values %a',
      OP       => 'scalar grep { $a{$_} !~ /^$/ } keys %a',
   }
);
[download]