If you have a router and Internet works with any application/site but you can’t connect to any microsoft.com site (e.g. WindowsUpdate, Windows Live Messenger [error code: 81000306], etc.) you might have your MTU set to a too high value. The default MTU for ethernet devices is 1500 but since the PPPoE header adds 8 Bytes to the packets, they get fragmented. And the microsoft.com servers seem to not accept fragmented packets.
So the solution is to set your MTU to the best value for PPPoE: 1492. To do this, use a tool like the TCP Optimizer to set the MTU for your ethernet device to 1492. After a reboot, all microsoft.com pages should work again – including Windows Live Messenger.