Well, my HO is investigating the problem again, apparently they are going to look into the mail servers. I guess I will have to wait patiently for their analysis. I tried to get information on who hosts the server but they didn't tell me, they just replied that I've got a ticket number and that they're on it. I will post the resolution if and when they find it...(BIG if)