The following is only half an answer...
I had imagined that your case was one motivation for SPSS's distinction between user missing data (when you assign some values 9999 or similar) and user missing data (represented by the period). Your skipped questions would then get the first one. If that were true this would explain to recode things in SPSS syntax.
However, a brief read of the docs for the missing value imputation module suggests that both types of missing get imputed. So, coding doesn't seem to help get the right behavior and I'm no longer sure what the distinction is for.
Perhaps someone who uses SPSS more seriously than I ever have can confirm all of this? I'd certainly be interested in the answer. I'd also be interested in answers for R. MICE is the only strategy that springs to mind.
[later edit]
One possibility is to 'impute everything', even the structural missings that could not have been observed on logical grounds. To make things concrete assume three variables A (true/false), B, and C where B is answered only if A=true and C has missing data.
An imputation strategy that imputes B when A=false is then creating a counterfactual: the value B would have had, if A had been true. Even if this imputed value is ignored in subsequent analysis then in most MI routines both the actual value of A and the counterfactual value of B will be used to impute missing data in C. So it seems to me that the 'impute everything' strategy implicitly assumes that those imputations of C are relevantly similar to the ones that depend on A when A=false but on both A and B when A=true.
This is the thought that motivates by MICE suggestion. A set of hand-written chained imputation equations could presumably be selective about the subset of things it imputed with.
The other approach - the one I think @ttnphns suggests - is to separate the data set into cases where A=false and where A=true, and then do separate imputations on each. This deals with the logical difficulty and involves no counterfactuals, but it also uses slightly less information because values of B where A=true should, at least in theory, be able to inform imputations of C where A=false, but won't in this scheme.
I've always felt this was a rather small price to pay and have used this strategy myself on several occasions (that's an admission rather than an endorsement). However, you say in comments that there are a lot of nested conditionals in the question structure. That would make this strategy less appealing.
Either way, the regressions you finally fit will want to take into account the stratification that the yes/no questions induce, and this seems to be another thorny issue. Perhaps some survey researchers have a standard procedure?