I've had the most luck using an app called Autoruns which you can download through Technet:
http://technet.microsoft.com/en-us/sysinternals/bb963902.aspx
In the zip file Autorunsc is a command line version which you won't need. The application will show you everything which auto loads on your computer. If the popups are mostly limited to IE, there will likely be some bad stuff on the Internet Explorer tab in Autoruns.
Most of the malware I've manually removed will have multiple registry keys reinstalling the bad software into IE. In Autoruns, you're looking at anything which shows up as "Not Verified" as the "Verified" items have been digitally signed by Microsoft. Just because it's "Not Verified" doesn't mean it's bad, but those are the items to question as they don't have digital signatures with Microsoft. I don't think I have ever come across "Verified" malware before.
Unchecking the box will keep the item from starting up automatically, and deleting it will remove it from the registry completely. If it comes back, something is re-enabling or reinstalling it. Use caution when removing stuff from the registry, whether with Autoruns, Regedit or any other program.
If you can identify the malware by using Autoruns but can't delete it because it's still running, you can use the task manager to try to find it (unlikely to work) or you can use another Technet tool Process Explorer which is like the Windows Task Manager on steroids.
http://technet.microsoft.com/en-us/sysinternals/bb896653.aspx
I like it because I can trace particular known bad dll files back to the parent process and manually kill a process and/or process tree.
In Autoruns and Process Explorer you can right click on an item and select "Search Online" to find out what the general consensus is regarding the file in question.
Here's a forum for Autoruns on the Sysinternals/Microsoft site:
http://forum.sysinternals.com/forum_topics.asp?FID=16
They have stickies for useful stuff including what not to uncheck from Autoruns as you can potentially hose your system if you aren't careful, just like editing the registry in any other way.
http://forum.sysinternals.com/forum_posts.asp?TID=5226
You don't need to rebuild your system, but for a lot of folks it's much easier and less painful.
I wouldn't recommend installing Linux or UNIX onto another system partition if it's not something you will use on a regular basis. Most of the bootable distros will give you read/write access to NTFS partitions. If you're interested in Linux, UNIX, BSD, etc. start here:
http://distrowatch.com/