problem with gmail maybe related to dns

ok so here it goes,
I was helping a company set-up a new server (MS Windows server 2003). After getting the files in place and what appeared to be everything running steady, they started encountering e-mail issues. They use tds mail which is run through g-mail. The thing is, all 7 of the computers they have, need to get the main email for the company. It seems to malfunction randomly and some of them wont get the emails while others will. they are all set up with Microsoft outlook 2007 through pop3 email settings, and all connect through a static DNS server. What all might be going wrong if at different times some of them are receiving the emails, and some of them aren't. Is g-mail ok to use through a DNS server? All accounts have checked "save copy of message on server".
Is this because of the networking, or because of the email settings.

Today a test email i sent went directly to the trash folder rather than the folder "TDS" which the new emails are supposed to be routed to. But the next email i sent went to the tds mail folder.

Any help would be amazing.
Thanks
-Paul