Windows Live Messenger - Firewall rules

I am running Windows Vista RC2 and I am having problems signing in to
Windows Live Messenger.

When I am in a public network, Messenger works fine. But it refuses to
sign-in when I am in my corporate domain. After several retries it connects
once, but shows no one as Online.

I am certain it is a Windows Firewall rule that is getting affected from
Group Policy (Our domain runs Windows Server 2003 Active Directory). On the
same laptop, same domain in Windows XP SP2, Messenger runs fine. So I am
unable to pin point on the problem. I tried allowing all inbound/outbound
connections, still no use. Disabling Windows Firewall makes it work fine
though.

Any tip will be appreciated.

Regards,
Venkat