We really do need "cancel up to" semantics for reliable behavior. Consider the case where the client has sent the query (or thinks it has) but the server hasn't received it yet. If the cancel request can arrive at the server before the query fully arrives, and we don't have "cancel all messages up through N" semantics, the cancel will not do what the client expects it to.
Keep in mind that in the case of a cancellation arriving really too early, i.e. before any messages have been received by the server, it will be totally ignored since at the time of reception there's nothing for the server to cancel yet. This may seem a bit exotic, although if you really want to provide air-tight cancellation semantics you could have the server track unfulfilled cancellation requests. In other words, if the server receives "cancel up to X" and is now processing X-5, the cancellation request is kept in memory until X has been duly cancelled.