Hmm... yesterday I test out this firewall... permit everything got no warnings...
Not too sure if the reinstallation is causing the problems... because this would Norton to read it as a new application... and keep prompting you...
Some security programs are just very sensitive.
Just to be sure, make sure Windows Live Messenger is not affected by viruses. I know of one virus that goes around infecting all EXE files.
Upload your copy of WLM to
Jotti or
Virus Total for a scan.