We report on utterance verification of putative recognitions in both open-set and closed-set recognition tasks using telephone speech. For open-set recognition, we report on rejection of out-of-vocabulary utterances. In a two-keyword task ("male" and "female") using 50% out-of-vocabulary utterances, utterance verification reduced errors by 60%, from 12% to 4.8% compared to our baseline rejection strategy. For closed-set recognition, we report on re-ordering the N-best hypotheses. In a 58-phrase task, utterance verification reduced closed-set recognition errors by 30%, from 6.5% to 4.5%.