This paper describes a new continuous mixture HMM version of the HMM-LR continuous speech recognition system. Each HMM output probability density function is characterized by a 34-component Gaussian mixture. The system performs comparably to the previous system (discrete HMM-LR) even though it does not use duration control requiring considerable computation effort. We also describe two new search methods; an A* algorithm based and a hybrid best-first search. These two new algorithms are experimentally compared with conventional beam search techniques. The A* algorithm based search has been found effective in reducing the number of phoneme verifications by half with little degradation of recognition performance.