Thank you all for your support.
I guess i owe a satisfation to all the guys that tried to help, so here it goes:
I had to get mad with the ISP that is providing our link so their network team move their asses and start to look where they should :P
The problem was that apparently our requests, by some strange reason, started to bounce between 2 routers... they are working on the case.
Once again, thank you all guys!
Now that i have more free time and less headches, I will try to help others 2...