If we removed just subroutine prototypes rom the language the proof would not hold any more. So the question is is there a more general proof that does not rely on prototypes?

Yes:

BEGIN {
   eval "sub foo {}" if rand() < 0.5;
}

foo 'x';
[download]

>perl -c test.pl
test.pl syntax OK

>perl -c test.pl
String found where operator expected at test.pl line 5, near "foo 'x'"
        (Do you need to predeclare foo?)
syntax error at test.pl line 5, near "foo 'x'"
test.pl had compilation errors.
[download]

Execution is required to decide whether foo is a subroutine call or a bareword.