I've actually solved the problem with a bit more fiddling, so for anyone else having the same problem I'll post the solution here. This is for Windows 7.

1. From the Start button, open Control Panel -> Programs and Features, uninstall DNS Unlocker.
2. After uninstalling, you'll get a popup saying that to complete uninstallation, you'll need to manually reset your DNS. Originally, I didn't know what this meant so just ignored it. That was the source of the problem.
3. To reset the DNS, from the Start button, go to Control Panel -> Network & Sharing Center -> Local Area Connection -> Properties -> Networking tab -> Internet Protocol Version 4 -> Properties. You'll find that the DNS addresses have been set to a couple of hard-coded IP addresses. This is how DNS Unlocker works; instead of using a 'safe' DNS, it redirects your browsers to its own DNS servers, which insert all the junk ads into your web pages.
4. In the above dialog box, select "Obtain DNS automatically", and click OK or Close all the way out of the dialogs. This will restore the DNS servers to be those provided by your ISP.
4a. If you use a VPN, you'll need to repeat this process for "Local Area Connection 2" in the Network & Sharing Center.
5. Finally, you need to reset your browsers to their default state. In Chrome, open the Settings page using the icon shaped like 3 horizontal lines in the upper right corner. Click on "Show advanced settings" at the bottom of the page, then scroll down to the bottom and click the "Reset settings" button. After that, DNS Unlocker has been removed from Chrome, though you'll need to reactivate any extensions you want Chrome to run. Do that by clicking on the Extensions link in the upper left of the Settings page.
6. For IE, press the gear-shaped icon at the upper right and select Internet Options. Click the Advanced tab, then press the Restore Advanced Setting button, then Apply. Finally, click the Reset... button, then select the "Delete personal settings" checkbox, then Reset. After restarting IE, DNS Unlocker should be gone.

Resetting Firefox, Opera and Safari doesn't seem to be needed.

As far as I know, DNS Unlocker doesn't leave any malicious files or registry entries after you uninstall it using the Control Panel, so running all these malware cleaners won't do any good. The problem is that it changes your DNS host and uninstalling it won't change it back.

Hope that helps.