I figured out that messenger must be using the full name field from
edir to populate usernames in the contact list and within messenger.

Question is, how does one get the display name to change within
messenger? I've changed the full name field on a couple users, also
had to add an entry to the field for a few that did not have it.

Many of the users that did not have a full name field entry started
generating the error when others would log in:

The listed contacts no longer exist in the Messenger system. Click OK
to remove the invalid contacts from your contact list.

The OU's that these users live in are part of the messenger setup.
What would be causing them to become invalid?