I tested it very carefully before writing this post using alts and found the same.
Said so in the OP and tried explaining it to North but they have an odd idea about how it works. I'm very experienced with both programming and databases though so it looks incredibly obvious to me. I suppose if you're not used to thinking in those terms the plot permission logic could be confusing.
That would be the simplest solution - but only to one part of the problem. It doesn't address others.
And yes it should be simple. Plot security is probably handled via some form of SQL and the above would just be a matter of adding a basic OR [structure setting = public] statement into the check.
But if that's simple and do-able then so is everything I suggested in the OP. The amount of code controlling plot permissions would be very small and basic.
Effectively most of what I suggested is just removing one AND statement, i.e. just check the structure permission setting rather than both the plot and structure. Simple. The majority of the work would be in reconfiguring the plot/structure permissions UI to add the extra options.