yes to all of the above exept the mcfee one ...mcfee is sh1t
If you have tried Hijack This and found nothing when the message appears, that would suggest hat nothing is actually running. You did mention that everything else seemed OK?
So, let's say we just insert something into the boot cycle to produsce a message then vanish? you won't see a process running will you.
This seems to be a teaser?
Try http://www.winpatrol.com "WinPatrol" and:
Use the tools to look for weird stuff in your startup or the Windows "hosts" file?
It is the next logical step?
If all else fails, reformat and reinstall it. I have many times.