Clean Registry/Files BEFORE Starting Windows?

I'm getting tired of some spyware perfectly laced into my XP os that they become next to impossible to remove.

Is it possible to have my C++ coded app launch just before Windows starts and have it make changes to my registry (ie. flush out the AppInit_DLL area) or remove files off the system. Once WIndows loads up having the many spyware apps already running makes it difficult to queue such actions up -- I've tried to flush out AppInit but after a few milliseconds it is put right back by some unidentified process. The Pre-WIndows area, where CHKSDSK or Partiton Magic's tool launch, intrigues me. Perhaps such a location could be used for sweeping. How do i launch my app here?

Please no responses from the over-paranoid. I just want a constructive answer.

Thanks.