I can't provide any specifics (because thankfully I have no access to Outlook or Exchange these days), but some things to consider:

Outlook and Exchange are built around the idea that both the client and server live on the same LAN. Keeping Outlook in it's default mode is likely bad if they are using a hosted Exchange service across the internet. This method of accessing the server is usually called MAPI.

Outlook does have an "offline" mode and can cache the server info, allowing a user in an office to take a laptop home, and keep access to any previously downloaded e-mail. I want to say this is also referred to cached mode as well. Based on the popups about access being restored, it sounds like this mode might be active.

Outlook also has a setting somewhere to talk to the Exchange server using the ActiveSync protocol. This is a Webdav protocol using HTTP, instead of MAPI, and is how the iPhone is accessing the server. This is probably the best way for Outlook to also be configured, since the server is not on the customers LAN.

Odds are, the tray icon is momentarily flashing messages about connectivity issues, since MAPI isn't really built to traverse the internet. We saw similar issues at my previous job when the Exchange server was moved offsite and into a datacenter that had some initial bandwidth issues.