You did not say HOW you removed McAffee.
Security applications (firewalls, AV, etc) normally require very careful removal prcedures as they use very complicated links to the many inside items in Windows.
If you did not use their uninstallation procedure, chances are that everything that should be uninstalled wasn't.
That would include the spam filter connection to Outlook which a clean uninstaller should/would/might remove.
If possible, I'd reinstall McAffee again and then use their uninstaller to clean up.
When all is clean, you can follow up with CCleaner.
If you did use their uninstaller and cleanup, then perhaps you could tweak Outlook in Tools > Options, I believe, by unclicking the McAffee spam addins. Just a guess.
Disclaimer: I do not and did not have McAffee, so above is based on reading the forums.
Edited - here's a link to McAffee removal toolhttp://www.softpedia.com/get/Tweak/Uninsta...oval-Tool.shtml
Edited by tos226, 28 October 2007 - 08:33 PM.