Autocomplete errors on internal exchange emails

We recently switched the company from a hosted exchange to our own Exschange 2016 server. When we moved everything over we would get bouncebacks on inteal emails. I found the cause of this to be Outlook's autocomplete, the solution was basically to remove the autocomplete entry and then recreate it and it would now point to the new server.

However today a new one crept up, the reply all button. When this is selected we are getting the same issue, despite the individual autocomplete entries being corrected already. How would I go about fixing this for all the employees?