Unlike pragmas that affect the `$^H' hints variable, the `use vars'
and `use subs' declarations are not BLOCK-scoped. They are thus
effective for the entire file in which they appear. You may not
rescind such declarations with `no vars' or `no subs'.
[download]

Note the phrase entire file. So, when you declare $qux, $quo, and $zip in foobarbaz.pl, perl has already forgetten that they were declared via use vars by the time you get around to reading them in program.pl. However, the symbol table is more permanent, which is why you can still access them by explicitly specifying package main.

Update

Whoops, guess you shouldn't always believe the docs... it does look like the behavior follows chromatic's explanation.