Presuming you've already read this.
I can't believe that you have properly reformatted your computer...
Plus!
does work on a clean install of Windows XP, Vista or 7 with the latest Windows Live Messenger.
Plus! disappearing after restart is a classic example of conflicting software, as you're aware of.
There's always the possibility that some conflicting software hasn't yet been acknowledged.
All I can suggest is that you post a list of installed programs.
This can be done with CCleaner, Belarc Advisor
or [will edit with better options]...
/ 
