Using CCleaner is completely differant than uninstalling. Using CCleaner will not solve anything. Not to mention that polygamy has got nothing todo with any registry key or temporary file or whatever else CCleaner might try to "fix".
If you want a complete clean install I suggest you remove the main registry keys and the user specific local data files of MSN Messenger and Windows Live Messenger manually (
like so). CCleaner will not be able to do that.