But script execution only occurs when a new block is created/validated, and at that point in time the "current best block" is the block including the transaction. Are you making a distinction between input height vs output height?
Yes, that's probably a better way to do it. INHEIGHT and OUTHEIGHT
My understanding was that a tx is checked to be not-malformed when included in a block but the scriptPubKey is only evaluated when the tx is spent. We can send to arbitrary P2SH addresses so I don't see why the scriptPubKey would be an issue.
And no, hard forks are not required for proof-of-x systems to be implemented in bitcoin. That's just required in the braindead way they've been handled in alts.
The only way I could think of adding PoX into Bitcoin without a hardfork is to keep PoW as it is and add PoX as an extra constraint which is stored in the coinbase scriptsig perhaps. If the majority of clients are new then the blockchain will be validated according to these new rules but the small proportion of older clients will still validate PoW as usual. However, if the difficulty decreases due to the extra constraints then there's the potential for an attack on old clients by ignoring the new constraint and just mining PoW.
That said, I don't think that is an elegant way to do it. Have there been other suggestions?