I would have recommended VX2Finder if you would have told me about in Ad-aware. It is a nuisance to get rid of. And you are correct, sometimes it shows up in Hijack This logs, sometimes it doesn't. Well done for removing it anyway.

Have a read of this info to prevent the problems returning:
Preventing it returning

After your problem has been resolved on the forum, it is an absoulute MUST to do the following steps to prevent the problem returning. Click on the link to get access to the software or webpage that I'm referring to.

1. Visit Windows Update
Pay a visit to Windows Update and scan for and download ALL Critical Updates and Service Packs. New updates are usually released monthly so check back to Windows Update every month.

2. Download Antivirus Software-
If you haven't already got Antivirus software, you should download and install AVG Antivirus. It is freeware and is updated nearly every 2 days (sometimes more frequently if there are a lot of new viruses) and in my opinion, is better than some Antivirus software such as Norton. Antivirus software will prevent viruses infecting your system and it is important that you update it every two days or every week at the most.

3. Download a Firewall-
If you haven't already got a firewall, it is Very important that you download one. Firewalls will prevent unauthorised access to your computer and stop data leaking out of your computer. You may think that it won't happen to you, but Hackers don't care who you are, what you do, where you live or what you had for tea last Sunday on your holiday in the Lake District, they want your data. Firewalls will keep these sneaks out and one of the best is Sygate Personal Firewall, which happens to be freeware.

4. Spyware Scanners-
It is important that as well as having real time spyware protection, you have a spyware scanning application. If you have not already been told to download one earlier in this thread, it is a good idea to download Spybot Search And Destroy and Ad-aware. They are both spyware scanners and will search for a remove spyware. It is recommended that you have both, because one will pick up entries that the other misses. It is even a good idea to download these if you have other programs such as ASE, Spysweeper, Pest Patrol, etc, because one spyware scanner will not pick up everything. Please remember to update your spyware scanners weekly/fortnightly.

5. Prevent Spyware slipping through Internet Explorer-
Quite a lot of spyware slips through Internet Explorer if your settings are not tight enough. Spyware Blaster will help you prevent spyware slipping through and installing tracking cookies. Simply run it via Start> Programs> Spyware Blaster and click Enable All Protection and it will protect you. It doesn't even have to be open! Remember to update weekly/fortnightly.

6. Constant Spyware Protection-
It is important to have constant spyware protection. Spyware Guard works like an antivirus program but detects Spyware instead. It will constantly protect your system. Check for updates monthly.

All Of these steps are very important and it is HIGHLY recommended that you download all of the programs mentioned for your own safety. Remember to Update everything (including Windows using Windows Update)! It is also a good idea to perform weekly/fortnightly scans with Spybot S&D, Ad-aware and your antivirus software.

And last of all, please remember, that common sense is your greatest tool. Without it, spyware and other related Malware would rule!