In this correspondence, the performance and complexity of channel-optimized vector quantizers are studied for the Gauss- Markov source. Some interesting observations on the geometric structure of these quantizers are made which have an important implication on the encoding complexity. For the squared-error distortion measure, it is shown that while the optimum partition is not described by the nearest-neighbor rule, an operation equivalent to a Euclidean distance measurement with respect to an appropriately defined set of points (used to identify the encoding regions) can be used to perform the encoding. This implies that the encoding complexity is proportional to the number of encoding regions. It is then demonstrated that for very noisy channels and a heavily correlated source, when the codebook size is large the number of encoding regions is considerably smaller than the codebook size - implying a reduction in encoding complexity.