I just reread this thread, and noticed that you have used Windows system restore.
The problem with Windows system restore is that it 'breaks' McAfee. If you have McAfee on your system and go back to a previous state, you end up with a McAfee that is partly 'new', partly old, the same may be true for the operating system, since McAfee has so many hooks in the operating system. I can't rule out that it's too late to fix everything without a reformat because of this.
About the service pack 3: there have been issues about installing and uninstalling (beta versions of ?) IE 7 and IE 8.
I found a link, am not sure if it's the latest, but you can try:
http://service.mcafee.com/FAQDocument.aspx?lc=1033&id=TS100507If necessary you could try booting in safe mode (press F8), and log in as administrator or use another account.
Not mentioned in the FAQ is that it's a good idea to remove any leftover McAfee files (hidden or not) before installing McAfee again. But it may not be necessary.
When you install it's best to install from your online account.