Going out on a limb here, but I'd say the assumptions about missingness of a variable do not depend on the availability of values within the known variables. Instead, they depend on the proposed theoretical mechanism of missingness, and given enough additional and related variables in your dataset might be estimated based on the MAR assumption.
what I mean is the following. Take your example, where you have X, Z, Y. Initially there's only missings in Z. If you assume MAR based on $P(Zmiss) = f(X,Y)$, then that's true regardless of $X$ or $Y$ being available for the rows with missing data.
Now if you have missings in X as well, things do become more difficult. But do no fear! If the above MAR assumption is true, then what's also true is $P(Xmiss) = f(Z,Y)$ and $P(Ymiss) = f(X,Z)$. (this means you could use these variables to estimate missing values in both ways!)
So long $P(missingness)$ in $Z$ or $X$ is not dependent on the missingness of itself or the other (which would be some kind of difficult MNAR, which we assumed it isn't by stating we think it's MAR), imputation should handle this just fine.
Another thing which might be good to know about multiple imputation in this context is that multiple imputation functions (at least R's mice does this) often use strategies where your dataset is initially completed with random draws.
Only after this, in the first iteration of imputation, the appropriate imputation models estimate replacement values based on the apparent associations within your data. The first random replacement draws are thus replaced by estimates based on the MAR assumption.
Especially in the context of having more than one variable with missing values (where the imputation function has to start replacing missings for some variable), further iterations make sure the final estimates for all variables with missings are based on known data or data replaced by estimates (sounds weird I know), and end up close to the proper parameter space of the variables with missings.
What this completion and iteration also solves, is the problem of rows with both $Z$ and $X$ missing: as all data is complete from the start (albeit random guesses in the first iteration), all rows can be used at all times/iterations.
**Do note, the replacement estimates for specific rows where multiple values are missing, will very likely show more variation across final imputation sets than those where only a few or 1 variable was missing.
