I don't know much Windows stuff, but I have a couple of ideas. Currently, it's not clear to me what exactly the problem is. Yes, you can't connect, but why exactly ? Where does the chain break ?
So far, the advice you were given covers everything I would have thought of (and then some), so I don't know what else to add. But maybe we can figure out what exactly the problem is.

So, one thing to try is to ping from the laptop some host in the outside world; do this _without_ resolving names (dunno if this is default on XP, it is on the 2k box I'm typing this atm; if not, it should have a switch to tell it not to resolve names). If the ping works, then we've narrowed down the problem to some DNS issue; if it doesn't, we can stop trying to fix the DNS, since it's a lower level problem.

Another thing we could try is, like I said earlier, to figure out where exactly it stops. I'll assume that the firewall rules for allowing the laptop outside are correct (on all existing firewalls). If your firewalls allow you to do logging, please enable it, and see if something gets recorded when you try to access the outside world from the laptop. Do this with all the firewalls involved (laptop, desktop, modem if applicable).

If your firewalls do not allow logging, or not to a sufficient extent, what we can try is to use something like Ethereal (ethereal.com). Don't panic at the idea of "network analyzer", it's extremely intuitive and easy to setup and use. And it's free and multi-platform. You can set this up first on the desktop, and sniff packets from the laptop - preferably on the WAN interface, to see if the packets even make it all the way there. Hopefully, they don't, so we know that the problem is somewhere before that point. In either case, this will narrow down the possibilities and help us localize the problem.

If anybody else has other ideas, please feel free to correct me or suggest better approaches.