This paper deals with the recognition of spelled names over the telephone. It introduces an efficient way of handling the spelling grammar, that is the lexicon of the allowed spelled names. The proposed approach is based on a forward-backward algorithm. The constraints on the sequences of letters are derived from the lexicon and are used by the A* algorithm in the backward pass. This forward-backward approach is compared to a 2-pass ap-proach, which relies on a discrete HMM based retrieval procedure. The rejection of incorrect data is also investi-gated, based on the comparison of a lexicon constrained solution with an unconstrained decoding. The ap-proaches are compared on field data collected from a vocal directory service. Results are presented for the recognition of valid spelled names and for the rejection of incorrect data (non-spelling and noise tokens and spellings not in the lexicon). The results show the efficiency of the proposed forward-backward procedure.