Okay, so I read the first sentence and failed to read that you already tried the cleanup tool.
You can contact OneCare Support -
How to reach support (FAQ) - http://social.microsoft.com/Forums/en-US/onecareinstallandactivate/thread/30400b52-7f26-4ba0-bc18-17e305329d90
Or you can try this program which purports to be able to clean up just about anything installed on the PC that doesn't uninstall cleanly - Revo Uninstaller - http://www.revouninstaller.com/revo_uninstaller_free_download.html
-steve
~ Microsoft MVP Windows Live ~ Windows Live OneCare| Live Mesh|MS Security Essentials Forums Moderator ~