Windows Messenger seems to think it has a "direct connection (no firewall)"
even though I connect to the internet through a D-Link NAT Router (which
supports uPnP).

Is that correct? What does your say?