Hi Russ Fletcher,
Welcome to Microsoft Q&A Forum! Have a good day and i hope you're doing well!
I’ve done some testing on Android devices to replicate this behavior. It’s helpful to understand that there is a distinction between the Outlook App's internal data and the Android System Address Book (the native contacts app on your phone).
Synchronization is often a two-way street. To help us narrow this down, could you confirm if all the contacts you see are purely created in Outlook, or is there a chance some contacts were originally on the phone's local storage and synced up? Also, please check Outlook App > Settings > Contacts > Sync Contacts to see if this is toggled ON.
Based on my research and your description, the most likely scenario is that while the contact has been successfully deleted from both the Outlook Desktop and the Exchange Server, and is confirmed to be absent from the Recycle Bin, the Android System Address Book is still holding onto a cached copy of the old record. This essentially means that although the Outlook app has updated its internal data, it failed to trigger the necessary cleanup command to the Android native storage, causing those specific entries to remain visible on your phone as ghost records.
To resolve this, please try forcing a System Re-sync to clear the Android Cache:
- Go to Android Settings > Accounts (or Passwords & Accounts) > Manage Accounts.
- Select your Outlook account > Sync Account.
- Toggle OFF the Contacts switch.
- Wait a few seconds (this allows the system to dump the cached data).
- Toggle ON the Contacts switch again to force a fresh download of the correct contact list.
If the issue persists, you may need to try resetting your Account within the Outlook app or deleting and re-adding the account entirely. You can find detailed instructions for these steps in this official Microsoft article: Can't sync calendar and contacts with my phone or tablet.
Additionally, could you confirm if you are using a Business/Organization account or a Personal one? Have you double-checked the contact count on Outlook on the Web (OWA) via a browser to see if it matches the Desktop count?
I hope this information gives you some insights into why this is happening. If you have any further questions or concerns, feel free to let me know.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.