From the sounds of it your system has something nasty locked into the windows start-up routine that your AV software cannot shift (it's kicking in before the AV software is, and though you should be able to 'deny access', the program will always stay there)
Have you tried booting into safe mode and running your AV software then, or going for a system restore from safe mode (choose a date before the problem occurred)?
*Doing a system restore in safe mode should work better than from normal windows as some programs can prevent a restore from completing.
If not then that is usually the best way to sort out a problem like this. If you have done this and the problem is still there then you might be looking at having to do a full re-install. That being said I've never known the safe mode fix to not work in getting rid of persistent crap that AV software might struggle to remove.