I don't understand why you say my proposal would make the protocol more stateful. I think it doesn't.
Each reply is only  the result of the current request only, and there is no new session information.

I also wondered this. My first thought was that it's basically the same as the PING message, a nonce that is repeated immediately on reply. This makes it easier to multiplex operations over a single channel. I'm not against this basic idea, and it is easy to ignore for clients that don't want to use it.

I think the state comes in here:

      - inv sends back the requestid given in getblocks or a special value in case of a notification.
      - addr sends back the requestid given in getaddr or a special value in case of a notification.

"*command1* sends back the requestid given in *command2*".

This requires keeping state on the connection between command1 and command2. Arguably, this state already exists in the current protocol, but I'd rather see it reduced than extended.

Also... Many of the described commands don't need this as they already have a natural "nonce". For example, the id of the requested block header. If this is passed in the reply, and the caller can correlate the request and reply without a special nonce administration.

Wladimir