When is an answer a nanswer?

While I'm happy I've written this, I'm unsatisfied with it as an answer to what I've concluded is the heart of your question, namely why there's no way to get EVAL to violate the principle that lexical symbols are frozen during compilation.

Aiui the rationale boils down to A) avoiding dangerous security loopholes, and B) it not being considered worthwhile allowing for violation under some MONKEY pragma.

But whether that's accurate, and discussing that, and any possibilities a Rakudo plugin could enable violating the lexical principle, is far beyond my paygrade.

I'm tempted to copy this answer into a gist, link to it from a comment on your question, and delete this answer.

Alternatively, if you agree there's this gaping hole in my answer, perhaps you'd be so kind as to unaccept it, and then I can put a bounty on it to try get an answer from jnthn, and/or encourage others to answer?

Quick fixes

Add a package qualifier:

package Foo {
  our sub outer {
    EVAL 'say $Foo::bar'  # Insert `Foo::`
  }
}

$Foo::bar = 'bar';
Foo::outer; # bar

or:

Use a lexical (compile-time) symbol:

package Foo {
  our $bar;          # Create *two* symbols *bound together*
  our sub outer {
    EVAL 'say $bar'  # Use *lexical* symbol from *lexical* stash
  }
}
$Foo::bar = 'bar';   # Use *package* symbol from *package* stash
Foo::outer;          # bar

(It might help to read the opening part (up to "so: our $foo = 42; Is doing this: (my $foo := $?PACKAGE.WHO<$foo>) = 42;") of jnthn's answer to a fairly unrelated SO question.)

Initial answers to your questions

why are symbols created at runtime not available to EVAL?

They are available.

But:

Symbols created at run-time can only be created within some existing or new symbol table hash (aka "stash"^[1]) (which stash must have some symbol naming it, which symbol in turn can only be created within some existing or new stash, and so on recursively);
The stashes for such symbols must be package stashes (using the built in Stash type), not lexical stashes (which use the PseudoStash type).
Any reference in code to a package symbol must name the enclosing package(s) as part of that reference.

So, for example, given a $foo::bar = 42; statement declaring a symbol $bar at run-time in a package foo:

A $bar symbol would be added to a package stash (Stash) associated with the package foo;
The package foo, and its associated stash, would in turn be created if it did not already exist, along with a symbol foo being added to the existing package stash corresponding to the package containing the $foo::bar = 42; statement.

And then, to refer to the $bar symbol you would have to write $foo::bar (or use one of the other forms of package qualified references such as foo::<$bar>). You are not allowed to refer to it as just $bar.

why are symbols created at runtime not available to PseudoStashs?

The built in PseudoStash type is used by the language/compiler to stash lexical symbols at compile-time.

For discussion of the rationale for this distinction between lexical and package scopes/symbols/stashes (and complications such as the our declarator's use of both; and the fact one can create lexical packages), see the answers to What is the difference between my class and our class?.

All about stashes

There are two built in stash types:

PseudoStashs are for lexical stashes The language/compiler adds (static) lexical symbols^[2] to lexical stashes at compile-time. User code can only indirectly modify lexical stashes using language constructs that do so as part of their operation (eg my $foo and our $bar both add a lexical symbol to a lexical stash).
Stashs are for package stashes The language/compiler adds package symbols (at compile-time or run-time) to package stashes during compile-time or run-time. User code can add, delete or modify package stashes and package symbols.

Lexical stashes

These are managed by the language/compiler and frozen at the end of compilation.

You can add whole new lexical stashes, and add to existing lexical stashes, but only by using language constructs under the language's precise control such as:

A { ... } lexical scope. This will lead the compiler to create a new lexical stash corresponding to the scope.
package Foo {}, use Foo;, my \Foo = 42; etc. The language/compiler will, as part of compiling these statements, add a symbol Foo to the lexical stash corresponding to the innermost lexical scope containing such a statement. (For the first two it will also create a new package stash and associate that with the value of the Foo symbol. This stash will be accessible via Foo.WHO or Foo::.)

You can refer to lexical stashes, and the symbols within them, by using various "pseudo-packages"^[3] such as MY, OUTER, CORE, and UNIT.

You can assign or bind to an existing symbol in these lexical stashes using pseudo-packages associated with lexical stashes:

my $foo = 42;
$MY::foo = 99;    # Assign works:
say $foo;         # 99
$MY::foo := 100;  # Binding too:
say $foo;         # 100

But that's the only modification you can do. You cannot otherwise modify these stashes, or the symbols they contain:

$MY::$foo = 99;          # Cannot modify ...
BEGIN $MY::foo = 99;     # Cannot modify ...
my $bar;
MY::<$bar>:delete;       # Can not remove values from a PseudoStash
BEGIN MY::<$bar>:delete; # (Silently fails)

EVAL insists that unqualified symbols (no :: within the reference, so references like plain $bar) are lexical symbols. (For the rationale, see the SO I linked near the start.)

Package stashes

Package stashes are created by the language/compiler as needed according to user code.

Like lexical stashes, you can refer to package stashes via some "pseudo-package" names.

This...	refers to the package stash associated with...
`OUR::`	the scope in which the `OUR` appears
`GLOBAL::`	the interpreter
`PROCESS::`	the process in which the interpreter is running

Symbols can be added to package stashes due to the implicit meaning of language constructs such as an our declaration:

our $foo = 42;

This adds a $foo symbol to both the lexical stash corresponding to the innermost enclosing lexical scope, and a package stash corresponding to the scope:

say $foo;      # 42  (Accesses `$foo` symbol in enclosing *lexical* stash)
say $MY::foo;  # 42  (Same)
say $OUR::foo; # 42  (Accesses `$foo` symbol in enclosing *package* stash)

Unlike lexical stashes, package stashes are modifiable. Continuing on from the code above:

OUR::<$foo>:delete;
say $OUR::foo; # (Any)
$OUR::foo = 99;
say $OUR::foo; # 99

All of which leaves the lexical stash untouched:

say $foo;      # 42
say $MY::foo;  # 42

Package stashes can also be added due to the implicit meaning of user code:

package Foo { my $bar; our $baz }

Without a scope declarator (eg my or our) ahead of the package declarator, our is assumed. Thus the above code would:

Create a new Foo symbol;
Install two copies of that Foo symbol, one in the lexical stash corresponding to the innermost enclosing lexical scope (accessible via MY::), and the other in the package stash corresponding to the scope (accessible via OUR::);
Create a new package stash, and associate that with the Foo type object, accessible by writing Foo:: or Foo.WHO.

So now this will hopefully make sense despite any initial surprise:

package Foo { my $bar; our $baz }
say  MY::Foo;        # (Foo)
say OUR::Foo;        # (Foo)
say  MY::Foo::.keys; # ($baz)
say OUR::Foo::.keys; # ($baz)

The value of the Foo symbol in the MY lexical stash is exactly the same as the one in the OUR package stash. That value is bound to another package stash as accessed via Foo.WHO aka Foo::.

So MY::Foo::.keys and OUR::Foo::.keys list the same symbols, namely just $baz, which is in the Foo package's stash.

You don't see $bar because that's in the lexical stash which corresponds to the same surrounding scope as the Foo package but is nevertheless a distinct stash. More generally, you can't see $bar from outside that braced code because a key Raku design element is that the user and compiler can rely on purely lexically scoped symbols being 100% encapsulated due to their lexical nature.

Whereas you can't even see any lexical symbols from outside their lexical scope, you can not only see but modify any package symbols from wherever you have access to the symbols corresponding to their enclosing packages:

package Foo { our sub qux { say $Foo::baz } }
$Foo::baz = 99;
Foo::qux; # 99

A line like $Foo::Bar::Baz::qux = 99; will if necessary autovivify any non-existing package stashes, which can then be seen using a package stash reference such as the pseudo-package OUR^[4]:

$Foo::Bar::Baz::qux = 99;
say OUR::Foo::.WHAT;           # (Stash)
say OUR::Foo::Bar::.WHAT;      # (Stash)
say OUR::Foo::Bar::Baz::.WHAT; # (Stash)
say $Foo::Bar::Baz::qux;       # 99

EVAL will happily use symbols added at run-time provided references to them are suitably qualified:

package Foo { our sub bar { say EVAL '$OUR::baz' } }
$Foo::baz = 99;
Foo::bar; # 99

Footnotes

^[1] They're called "stashes" because they're symbol table hashes.

^[2] The abstract concept "symbol" is implemented as Pairs stored in stashes.

^[3] The term "pseudo-packages" is perhaps slightly unfortunate because a couple of them are aliases of Stashs rather than PseudoStashs.

^[4] For references like Foo::Bar, which do not start with a sigil but do contain a ::, you need to ensure you adhere to Raku's rules for resolving such references. I'm still working out what those are precisely, and intend to update this answer when I've got that nailed down, but I've decided to post this answer as is in the meantime.