I have a queer problem where users on the outlook cannot send and receive mail [Send/receive error].

This has been a pain for more than two days and i cant seem to find a resolution. 

Facts: 

1. The mail is corporate gmail and accessing it from the web is possible, but just not acceptable. 

2. Google Sync can eliminate the problem but am using it only as a temporary measure.

Any ideas welcome