I created a distribution list on one of my users. The next day we put the
distribution list on the exchange with the same name. Then I went back to the
user computer and deleted the distribtion list ,that is in her contacts. When
she type part of the distribution list name it is still looking at the one
that was in her contacts even thou it was deleted from the contacts.

If it was in delected items would that be the reason.
Regina