I haven't really thought about whether the solutions with .*? are actually incorrect, but most of them will almost certainly go wrong if you extend the regex latern on with something that might force backtracking on the preceeding construct.
$ perl -wE 'say "yes" if "A BCZD ZA" =~ /^A(\s.*?)?ZA/'
Here I added an A to the end, which causes backtracking when there's no A after the first Z. Which in turn allows a match that was forbidden by your rules.
(Update: This is a general problem when translating "may not occur inbetween" to "minimum match": it's only the same under certain very fixed conditions. You can "rescue" such a solution by putting it in (?>...) non-backtracking groups, but I still recommend against it).
So maybe your example wasn't actually wrong (and I apologize for having called it so without any proof), but it's surely not very maintainable, because a very simple, innocent change can break it.