Viterbi Decoder - Symbol Alignment With a 1/2-rate convolutional encoder, $n$ bits are encoded into $2n$ symbols.

Assume we have a long encoded stream such as $[... s_0, s_1,  s_2, s_3, s_4, s_5, s_6, s_7, s_8, s_9, ..., s_{100}, ...]$. I want to extract a small portion from the middle of it, and decode it.

Starting from the symbol $s_1$, the data is decoded as follows:

$[s_1, s_2, s_3, s_4, s_5, s_6, s_7, s_8, ..., s_{100}]$ ---Viterbi Decoder---> $[b_1, b_2, b_3, b_4, ..., b_{50}]$

What happens if we start from $s_2$?

$[s_2, s_3, s_4, s_5, s_6, s_7, s_8, s_9, ..., s_{100}]$ ---Viterbi Decoder---> $[b_1', b_2', b_3', b_4', ..., b_{49}']$

Using Matlab's vitdec, starting from $s_1$ or $s_3$ produces the same result where the only difference is that $s_3$ starts from the second bit. But starting from $s_2$ produces a totally different vector, there is no small pattern in common between this and the results obtained when starting from $s_1$ or $s_3$.

Is this the expected result? Do we have to do symbol alignment to get correct results? Since the preamble in the data is encoded too, I do not know where to start decoding.
I find it surprising that it didn't matter where you started.  Normally incorrect symbol alignment will completely change your results.  The usual method for determining the correct alignment (assuming you don't have other information like a Frame Alignment Word to help you figure it out) is to try both possible phases and see which produces a lower path metric.

You can, by the way, do the same when the code is punctured, you just have more phases to try.