Hello Brady Passey,
Regarding this issue, if these users open Outlook Web App, whether OWA will shows the new added SMTP address? And the problematic Outlook client is Outlook for Windows desktop app? You
may let them hover over to the browser tab, or select one email they have sent or received to make sure the email address is updated.

If issue only presents itself in Outlook desktop clients, then it should be related to specific clients. In Outlook, please let them try online mode to see if issue persists: Outlook->File->Info->Account
Settings->double-click the account, untick “Use Cached Exchange Mode to download email to an Outlook data file” checkbox, then restart Outlook again and see the results.
If above method doesn’t help, you may let them test this issue in a new Outlook profile:
https://support.office.com/en-us/article/create-an-outlook-profile-f544c1ba-3352-4b3b-be0b-8d42a540459d .
If these end-users are using pure Exchange online service, let him try Office 365 SaRA tool to see if issue can be resolved:
https://diagnostics.outlook.com/#/. At the meantime, please check Outlook updates to make sure it is the latest version (Outlook->File->Office account->Update Options->Update Now).
To better know about your issue, if convenient, could you please share a screenshot of issue symptom with us for checking?
Best Regards,
Anna