Android Device loses Contact ID for text messages after every reboot

[Eddie Reeve]

Hello.

In our environment, we have WorkspaceOne and SEG (Secure Email Gateway) deployed with certificate based auth.   Our users sync their mobile devices via the SEG to our Exchange environment.

We have noticed that within the default MESSAGING (text) app, the CONTACT ID/label for each user gets removed each time the device is either:
1) Rebooted
or
2) Has an Android Security update deployed
or
3) Has the user based certificate renewed

For example:

Let's say I have a Contact in my Exchange mailbox with the name "Joe Johnson."    His phone number is 212-555-1212.   When i use the messaging app (text) to send a text to Joe, or if he texts me, I see his Contact name next to the text message. 
 
Now let's say one of the 3 scenarios above takes place.    The next time i go into my Messaging app, all i see for Joe is the phone number.   

After about 12 hours, the list is refreshed, and the contact labels return to the messaging app.

Any suggestions or comments would be appreciated!  Thank you!