We did have an issue at the start of the year / end of December but we phoned them up at they sorted it out.
Are you using a onsite exchange?
Also do you have any Spam lists enabled on your email server, i.e. somthing like this: SBL - IP Spam Filter - The Spamhaus Project