Tried all the solutions on the net but looks like I've got something uncommon happening so here's my solution:
1. Ran 'Windows Install Cleanup' utility (look for a file on the net called msicuu2.exe
2. 'Killed' anything with the word 'Live' in it (!)
3. Downloaded Windows Live Messenger 2009 from FileHippo (no reason other than an unfair suspicion that Microsoft are trying to drive me nuts, so lets see if another server has a version containing special magic dust that makes software work properly
4. Installed it and it worked. No idea why, but then mine is the Inspector Clouseau approach to computing.
