Avg is good, but it does miss a fair amount of things in my personal exp.
But yes, try avast or another virus scanner. (hell I keep Avast, Avg and Avira all on standby with Avast my fully installed Viri defender)
Also, Malware bytes, or adaware. Adaware used to be great but has went down hill over the years.
Then use a good registry repair program. Cant think of any off hand, but you can surely find something highly recommended at www.downloads.com
If all else fails, prolly best to start over fresh anyway and go with a reformat.
Best of luck to you. Viri do suck, but at the same time, fighting them up close and personal can teach you a lot in understanding how an operating system works.