Hi and thanks for the answer.
I made an investigation of my own. I reinstalled windows last night and tested again with AVG installed this time around. I was not redirected. I reinstalled windows once again, and installed avast and got redirected. I was starting to think that the problem could be my router or maybe google itself.
Then, a few hours ago I asked a friend of mine who works at a computer shop for his laptop which had Panda installed and tested again. Nothing happened. Then I installed Avast Portuguese Version and tested again, and voilá, it got redirected.
Keep in mind this was on a DIFFERENT LAPTOP, and connected to a DIFFERENT ISP (usb stick of another ISP). Then he connected to his WIFI, and still got redirected.. Then we tested on another pc connected to a Public Wifi connection, and it was still redirected
As I said all along, I know my pc is not infected. So something is happening here. Also, I'm using Windows 7 Home Premium and he his using Windows XP Sp3 and Windows Vista. All of them are Genuine, as they came pre-installed in the machines.
So what to do now?
Update:
Tested with Avira, Comodo and ZoneAlarm... working fine. Only avast is popping up security warnings and showing me the url4short thing. Also the lavasoftsupport page seems to be opening fine for half a second before redirection. Sometimes it shows the full page, and avast pops-up and it gets redirected.