I actually have two routers, and in neither could I find the DNS test you mention. However, on the same LAN I have three MSWin boxes, two XP and one 2k, and none of these have exhibited the same problem. Does this not rule out the provider?
I'm not sure - IIRC Windows uses a local DNS cache so it doesn't go through a DNS server every time. You can clear the DNS cache and try it again on Windows to make sure.
On my router (Westell something) the DNS test is under the Advanced->Diagnostics tab.
Peter