More info from the client:
"I can hit the send/receive button after I have sent myself an email and the email won’t show up for minutes, but if I switch to my “info” email address inbox and then switch back to my “steve” email address, the email will show.  Our email is definitely behaving differently than it used to.  I used to be able to email a picture from my phone to my email, then 5 seconds later hit the send/receive button on outlook and the email would be there.   Now it will only show if I switch between my email accounts.  As soon as I click back to my “steve” inbox, it will show."

The solution to this problem ended up being to delete the account from Outlook and re-add it. Once the users did that, everything worked great.