This issue is very common after someone's email and account has been reinstated. Clearing the recipient list usually solves this issue

In OWA

TO CLEAR INDIVIDUAL EMAILS

1. Log into the Outlook Web App
2. Open a new email and start typing the email address
3. When the address you want to remove appears, use the keyboard to select the email address
4. The press the DEL button on the keyboard.
   

TO CLEAR THE WHOLE AUTO-COMPLETE LIST

To be able to clear the whole auto-complete list using Outlook Web App you need to use the light version.

1. Log into the Outlook Web App – ensuring ‘Use the light version of Outlook Web App’ is ticked.
   
2. You’ll see that Outlook Web App will look different when using the light version.
3. Click on the ‘Options’ button at the top right of the window
   
4. In the left hand menu, click on ‘Messaging’
   
5. Under ‘E-Mail Name Resolution’ click ‘Clear Most Recent Recipients list’
   
6. Click ‘OK’ to complete the process.

In Microsoft Outlook

TO CLEAR INDIVIDUAL EMAILS

1. Create a new email message.
2. Selecting new email in Outlook.
3. In the To field, enter the name or address you want to remove. As you enter the contact information, the autocomplete list displays the available matches.
   
4. Press the Down Arrow key to highlight the entry you want to delete from the list.
5. Selecting to delete an email from the autocomplete list in Outlook.
6. Select Delete (the X to the right of the contact name). Or, press the Delete key.
   

TO CLEAR THE WHOLE AUTO-COMPLETE LIST

1. Go to the File tab.
   
2. Select Options.
   
3. In the Outlook Options dialog box, select the Mail category.
   
4. In the Send messages section, select Empty Auto-Complete List.
   
5. In the confirmation dialog box, select Yes.
   
6. Yes button in confirmation dialog to Empty Auto-Complete list