Shoutbox

Formating is a good solution, but it feels like giving up

Disable everything from booting up. If it still takes ages to boot up then you still have dodgy Services  and / or drivers.

Try disabling undeeded Services, as they take just as much to boot up as your "boot items" and drivers get loaded up before you even see the Windows GUI, so if that part is taking ages, id go through your drivers list and update them / remove virus drivers .

And id recommend Avira over AVG. it has far lower system requirements
(Computer: Pentium or higher, at least 133 MHz
Operating system: Windows 2000 (SP 4 recommended) / Windows XP and XP 64 Bit (SP 2 recommended) / Windows Vista 32 Bit and 64 Bit
RAM: 192 MB / 512 MB RAM for Windows Vista
40 MB free memory on the hard disk (more if quarantine is used)
100 MB temporary memory on the hard disk
Administrator rights are required for the installation)
And is more powerfull(But just use it temporarly to get rid of rouge viruses). Also try out SuperAntiSpyware (Its freeware).

Ifall that doesnt work, then its time to format