...but if you're not using a P2P program on your machine...everyone has access to the internet (surfing a webpage in Internet Explorer...for example)...?
It could be that your P2P program is consuming all internet bandwidth...but this wouldn't happen during queries, but more likely to happen when downloading. Still I'd expect the internet to be slow, not unavailable on the other PCs.
Perhaps the ports the P2P requires aren't open in the router's settings...but then it would deny access to your machine running the P2P program and allow access to other machines, not allow you access to the internet and deny everyone else...
Does everyone immediately regain internet access the moment you disconnect and close your P2P program?