I've gone as far as I know how....

The message to restart your machine could be related to one of the scans you ran or to finalize an update that was installed (I see in the screen shot that you are alerted to a MS Update).

The scans removed a ton of malware.....perhaps you should uninstall your outdated AVG 7.5 and replace it with an AV program that is current. You also need to install a firewall.

Run this: Disable/Remove Windows Messenger to remove Windows Messenger. Do not confuse Windows Messenger with MSN Messenger because they are not the same. Windows Messenger is a frequent cause of popups.

Please use add/remove programs to uninstall:
J2SE Runtime Environment 5.0 Update 6"
Java 2 Runtime Environment, SE v1.4.2"
Java 2 Runtime Environment, SE v1.4.2_09"
Java(TM) 6 Update 2"
Java(TM) 6 Update 3"
Java(TM) 6 Update 5"
Java(TM) 6 Update 7

Run C:\MGtools\analyse.exe by double clicking on it. (Note: if using Vista, don't double click, use right click and select Run As Administrator). This is really HijackThis (select Do a system scan only) and select the following lines but DO NOT CLICK FIX until you exit all browser sessions including the one you are reading in right now:

After clicking Fix, exit HJT.

Now Copy the bold text below to notepad. Save it as fixME.reg to your desktop. Be sure the "Save as" type is set to "all files" Once you have saved it double click it and allow it to merge with the registry.

None of this is malware.

Reboot and install:
Java Runtime

Tell me what problems you are still having.

 

After downloading Avast....then uninstalling AVG...you should run Avast and let me know what it reports.

PCTools Firewall would be a good choice.

All of these can be found HERE.

 

You are most welcome....

The pop up is a result of something you installed, or at least started to install.

I suggest you post in software regarding that issue. You could start by going into msconfig and one by one disabling some items to see what may be causing this. Be aware that msconfig is not a solution, just a diagnostic tool.

If you are not having any other malware problems, it is time to do our final steps:

1. We recommed you keep SUPERAntiSpyware and Malwarebytes Anti-Malware for scanning/removal of malware. Unless you purchase them, they provide no real time protection. They do not use any significant amount of resources ( except a little disk space ) until you run a scan.
2. If we had you use ComboFix, uninstall ComboFix (This uninstall will only work as written if you installed ComboFix on your Desktop like we requested.)
   
   • Click START then RUN and enter the below into the run box and then click OK. Note the quotes are required
   • "%userprofile%\Desktop\combofix" /u
     
     • Notes: The space between the combofix" and the /u, it must be there.
     • This will uninstall ComboFix and also reset hidden files and folders settings back to Windows defaults.
     
     
   • Delete the C:\combofix folder from combofix (if it exists)
   
   
3. Any other miscellaneous tools we may have had you install or download can be uninstalled and deleted.
4. If running Vista, it is time to make sure you have reenabled UAC by double clicking on the C:\MGtools\enableUAC.reg file and allowing it to be added to the registry.
5. Go to add/remove programs and uninstall HijackThis.
6. You can delete the C:\MGtools folder and the C:\MGtools.exe file. You can also delete the C:\MGlogs.zip
7. If you are running Vista, Windows XP or Windows ME, do the below:
   
   • Refer to the cleaning steps in the READ ME for your Window version and see the steps to Disable System Restore which will flush your Restore Points.
   • Then reboot and Enable System Restore to create a new clean Restore Point.
   
   
8. After doing the above, you should work thru the below link:
   
   • How to Protect yourself from malware!