For months I've had this same issue:
Windows Live Messenger fails to deliver some messages without ANY warning of failure.
After lots of troubleshooting, I've decided to foward port 1863 to the WIFI router that is directly connected to the internet access modem router and what do you know, it worked!
Turns out some of the messages we lost in the first router. Since there are two separate networks (the WAN and the DHCP internal private network), sometimes packets just didn't know where to go.
Modem Router Network: 192.168.1.254
WiFi Router Nework: 192.168.1.1 (WAN) / 192.168.2.1 (LAN)
TCP Port: 1863
Forward to 192.168.1.1