Do natural generalizations of P versus NP exist?
John, while your kind comments are appreciated, I confess that I don't understand how your question relates to the simple point I was making in the quoted remark.  All I was saying was that we do know various separations between complexity classes, like P&ne;EXP, MAEXP&nsub;P/poly, NEXP&nsub;ACC, etc.  So, if you believe that a particular separation, like P&ne;NP, is "too deep to be either proved or disproved in ZF set theory" (or whatever), then it seems to me that the burden falls on you to explain why you think that separation has to be independent of ZF, while other separations turned out not to be.  For this argument to have force, I see no necessity for the other separations to have the particular form you specified.

But to address your question anyway: well, the obvious challenge in answering is to find any complexity class A for which we can prove that A is strictly contained in NA, where NA is "the natural non-deterministic extension of A"!  (Indeed, as Robin points out above, finding such an A is equivalent to answering your question as you've stated it.)  And the only examples of such A's that I can think of are things like TIME(f(n)) (it was proved in the 1970s that TIME(f(n))&ne;NTIME(f(n)) for f(n)&le;n log*n, since NTIME(f(n)) can simulate time slightly greater than f(n)).  (An earlier version of this post claimed that was known for all f(n).  Thanks to Ryan Williams for the correction!)  So setting A=TIME(n) and B=NTIME(n) would indeed answer your question in the affirmative.  A more "natural" example will probably need to await a breakthrough in complexity theory.

[Endnote: I wish to clarify that I didn't give things portentous names like "The Shtetl Optimized this or that"---those were Sidles's elaborations!]