Issue with sending/receiving from Outlook 2013 on Windows7

Question

I got Windows7 and Office 2013 with Outlook2013. My colleague and myself (there are just two of us in the office) are having troubles with both sending and receiving emails. ONLY using the Windows Outlook2013 program. Using web base interface or reading/sending emails on a mobile,iPad is fine - immediate.

The office is rented from www.executivecentre.com and I don't believe that the issue has anything to do with their network. I booked someone to come and try to help to investigate.

The exchange server is located in the Europe and I was told by our admin that we are the only office from all around the globe that reported such issue. We try to so some http://www.speedtest.net testing and all looks ok. The admin reckons that it must be some issue between continents.

I am on Vodafone and my colleague is on Telstra mobile network. Even if we connect our mobile of iPad to the office wireless the email works immediately.

I tried to work from home using TPG provider and I had the same issue.

I tried to connect my notebook directly to the network via Ethernet cable opposite to the wireless router that we use every day. Right now Outlook worked both ways.

The issues is with both sending and receiving but I would say that receiving could work at times and still some emails could be sitting in Outbox for hours.

I tried to start Outlook in safe mode and it didn't help. I am using all the settings that the admin gave me.

There is a yellow triangle in the Windows taskbar for Outlook or the message "trying to connect" for a long time. Once the message disappears and there is "connected to: Microsoft Exchange" there are still message in the outbox.

Using ESET Endpoint antivirus as the rest of the company. I'll try not use antivirus tomorrow.

Any idea what is happening? Any suggestion how to debug?