Since the day that the DNS security flaw was disclosed, and my ISP (Sapo ADSL) applied the patches, I started to notice that DNS resolving got very slow. I checked the support page from Sapo, and no changes were made. Same two DNS servers were being used, and ironically, after pinging the second, I realized that it was "dead". I also tried to call for support to ask them wtf was going on with their DNS servers, but the operator didn't seem to be very comfortable with the term DNS, so I just gave up. Time to change.
I've heard about OpenDNS, some free worldwide DNS service, fast, reliable and secure. I had to check it out. Just configured my router to use the new DNS IP addresses, rebooted it and voilá. Browsing speed was back, better than ever.
So now, after about 2 months of use, I can only recommend it. You can even register to access some more detailed options, like content filtering and stuff like that. And when you surf to a URL that doesn't exist, instead of having the normal browser message that website is down, you are redirected to a suggestions page by OpenDNS.
Here's everything you need, these two IP addresses in your router / internet connection:
Primary server: 220.127.116.11 Alternative server: 18.104.22.168