This used to happen in XP with Service Pack 2. What is your XP version (Home/Pro) and which SP are you on (2 or 3)?
Before you do anything else, go to Microsoft Update and download and install any updates for your machine, both Critical and Optional. Then run MVT to make sure your McAfee DATs are up to date, and run a McAfee Quick Scan (you've already done a Full Scan, this is just a precaution).
If you've got spyware on your PC you can safely run Windows Defender alongside McAfee : they do different things, and don't conflict (on XP, at least). Download, install, and run a quick scan with that. See what - if anything - it finds. Its main benefit is that it closely monitors key system settings and alerts you if any unknown program tries to change them (you can tell it to trust programs, so the warnings aren't very frequent).
Tell us if you still get the messages - and if possible take screenshots of them and post them here. They usually contain useful information.