In this paper, we address the problem of improving recognition accuracy of spoken named entities in the context of dialog systems for transactional applications. We propose utilizing the knowledge of relationships, that typically exist in many applications, between named entities spoken across different dialog states. For example, in a bank customer database each customer name is associated with one or a few account numbers, addresses and vice versa. We utilize these relationships to build long-term dependency constraints in grammars (and thus in decoding graphs) representing these entities. This enforces the recognizer to use collective evidences from instances of all the entities to improve the recognition accuracy of each individual entity. Experiments conducted to evaluate our approach show significant accuracy improvements on a task of recognizing a person via a name and a location. ©2010 IEEE.