Emails are sent in plain text based on a box checked in the contact record. So, check the contacts which are being sent as plain text instead of HTML and determine if they indeed need to be set that way. These contacts MIGHT be in the individuals contact list or in the global list. The individual can't change the global list though, so the Exchange Admin must check them.
And, that brings me to part two of your question. The global contact lists can't be changed by the individuals. That's a server admin function. There are normally 3 global lists on the drop down list for the addresses in a new email. One is called "company name", a second is called "global list / company name" and the third is called "something I can't remember which is related to OWA". All 3 lists are identical though. When you set the individuals default contact list in their copy of Outlook, you should be setting it to THEIR exchange contact list and not their local PST file contact list. When they create a new email, they can choose to look at one of the 3 global lists, which will be displayed first by default based on server settings, or choose to look in THEIR contact list using the drop-down list to select from.