Most existing algorithms for the Generation of Referring Expressions (GRE) tend to produce distinguishing descriptions at the semantic level, disregarding the ways in which surface issues (e.g. linguistic ambiguity) can affect their quality. In this article, we highlight limitations in an existing GRE algorithm that takes lexical ambiguity into account, and put forward some ideas to address those limitations. The proposed ideas are implemented in a GRE algorithm. We show that the revised algorithm successfully generates optimal referring expressions without greatly increasing the computational complexity of the (original) algorithm.