Checking msconfig is a very good idea. Also, look under "Add and Remove Programs" to see if there are any programs that you don't recognize.

Do you have DSL or some automatic connection to the internet when you start up? If you do, try unplugging the network cable to your comp before your start up, then run spybot and adaware. Shut down, replug in the cable, the start back up. I think that might help.