I was going to say that wasn't true, but went back and looked at the last test program I was using and decided I hadn't tested that situation correctly.   Using code

BEGIN {
    my  $foo = 'foom';
    use lib $foo;
}
[download]

results in error messages

Use of uninitialized value in string eq at /usr/lib/perl5/5.8.0/i386-linux-thread-multi/lib.pm line 29.
Empty compile time value given to use lib at hotshot.pl line 5

Using your code

    my  $foo;
BEGIN {  $foo = 'foom'; }
    use lib $foo;
    printf "executing:  '%s'\n", join("', '", @INC );
[download]

returns the desired results

executing:  'foom', '/usr/lib/perl5/5.8.0/i386-linux-thread-multi', ... , '.'

Just to try something different I tried

BEGIN {  our $foo = 'foom';  }
    use lib $foo;
[download]

which also worked.

Another thing to put in the list of things to re-study.   Key is that "use" (and other pragmas?) are executed (at compile time) before surrounding code at the same apparent 'level'.   By enclosing code in a BEGIN block ahead of the "use" we force it into compile time execution before the following "use" is executed.   (Or something like that ;-)