Contact name suddenly missing
Not much you can do if they were exchange contacts. The messages will still be there because they were created before you removed the account that stored all your contacts. You could probably re-add the exchange account, and see if you can mass-move the contacts to your iCloud group in contacts - probably best to try this on a mac if you have one.