I have seen numerous posts about megaclick. There is no need to log all these hijack attempts. Megaclick URL, DNS, and search redirection is dependent of the MegaUpload toolbar. Uninstalling the toolbar removes the redirections. Also, you can shut off megaclick within the toolbar.
I hope this helps! I joined just to post this.
Edit: I see your post was edited to include this new information. Sometimes just deleting the toolbar, especially just the program files folder, will not fix the megaclick issue. The configuration is stored in the registry.