Example_Foo and Example_FooPhp4
I think the example is not a good idea, as it will introduce yet another naming convention. Since in this example packages will be proposed at the same time it seems more reasonable to make the PHP 4 version the first major version and the PHP 5 version the second following our guidelines.
I also want to mention that at this point internals has still not committed to what E_STRICT will really be, how it will progress etc. One possibility is that E_STRICT will get split up in E_STRICT and E_DEPRECATED. In this case this RFC should probably be extended to cover E_DEPRECATED as well.
Another "issue" is that there could potentially be new E_STRICT warnings to features not available in previous PHP 5 versions. In that case the policy was always to allow an increasing in the required minor version, but it would probably not be wise to move too quickly to this new minor version. For example PHP 5.3 might introduce an E_STRICT on a feature introduced in PHP 5.3. Fixing the E_STRICT would in effect mean to break compatibility to all previous PHP versions.
At any rate, I think its a good idea to pass this RFC now, push internals to further clarify and document E_STRICT and work on solutions to any issues that might arise due to lack of clarification.