Thanks for the help and suggestions.
I've been mostly using the XP server for diagnosing. As I said, I can see that the DNS queries are coming through and hitting the server. I can also see the server process the query and then send out a response. I've double checked this by logging outbound port 53 traffic through the firewall, so I know that the answers are going out. On the other end, I never see the reply. Running a sniffer outside just shows the request, no response.
I can't get a response by using telnet regardless of whether I'm on the LAN or outside on the Internet. I also thought of trying netcat, and it failed as well on port 53. So that should pretty much tell me that something is blocking it (and again, I can see the request come in and a reply head out, but it never makes it to the other end).
Yeah... I also figured that a reply from a different port probably wouldn't be accepted either.
I can not change the port that the XP DNS server listens on. When I try to edit the port for the Linux firewall DNS (I've been trying to change it in /etc/init.d/named) BIND says that it is starting up correctly, but then I don't see it listening when I run netstat. How can I query a DNS server on a different port anyway? I tried to find someway to do that but didn't have any luck.
At this point I'm still waiting to hear back from my email to my ISP. I think from all that I've done it definitely points to a problem at their end.