"If the idea of "a package scope boundary also being a lexical scope boundary" were actually implemented"

It kind of already is implemented in Perl 5.14, albeit with a change in syntax:

package Foo {
   my $foo = 123;
   package Bar {
      # can still see $foo
   }
}

package Baz {
   # cannot see $foo
}
[download]

"would it cause any programs to break?"

The change of syntax makes it opt-in. Use the old syntax; get the old behaviour. Thus nothing needs to break.

"would they have been correct programs anyway?"

Yes; it's perfectly reasonable to want to share a lexical variable between different packages. It's not a common need, I grant you. And if it were forbidden the sky would not fall; workarounds would be possible. But the ability to share a lexical variable can, in some cases result in much cleaner code than would be possible without it.