Can't receive emails that are sent from gmail, hotmail, aol accounts, maybe yahoo as well

I have been alerted that some people have had error messages when they have emailed me.
I have a perfectly valid email address, and the problem applies to all the email accounts in my small company.
But - we ARE receiving emails from some people...if there is a pattern, it seems to be that we are not receiving emails from gmail and hotmail and aol, but 'professional' (e.g. emails sent from a company account) email accounts seem to get through (we are certainly receiving some emails, but clearly we do not know if all are getting through)
I have tried emailing from a gmail account and get the following error message:
This is an automatically generated Delivery Status Notification

Delivery to the following recipient failed permanently:

    audrey@handsupholidays.com

Technical details of permanent failure:
PERM_FAILURE: SMTP Error (state 13): 554 5.7.1 <audrey@handsupholidays.com>: Relay access denied

We have the following configuration:
- our domain names are hosted by GoDaddy, and we do have email accounts set up by them, but we also have email accounts set up through Gmail (so I have an account: audrey@handsupholidays.com which I access through mail.google.com)
- my account is NOT on a server, but my colleagues' is (MS Exchange with Outlook 2007), and he has the same problem as me.
- we cannot receive emails sent from each other within the office either  

1:
2:
3:
4:
5:
6:

Delivery to the following recipient failed permanently:
 
    audrey@handsupholidays.com
 
Technical details of permanent failure:
PERM_FAILURE: SMTP Error (state 13): 554 5.7.1 <audrey@handsupholidays.com>: Relay access denied