We have cable connection. The computers (currently 4) are plugged into router which is connected to the cable modem. The router is set to DHCP mode and assigns local IPs to the computers, while having static outer IP itself. The problem appears (only sometimes) upon computer startup (or reboot), when XP loads up it cannot connect to DHCP (Request timed out). No amount of ipconfig /release and /renew, or computer reboot can fix that. The only way is to reboot the router itself. What confuses me that this problem has ever occured only on two of our 4 computers (all are using XP, but none of them have the same hardware), and is occuring pretty often (at least once a day) without any predictable pattern. Any info or suggestions where to look for solution would be appreciated :)

Sounds like your router might be going bad. Before you replace the router, replace the network cables and swap the ports between the good and problem stations. So, if the 2 computers that are having this issue are on ports 1 & 2 of the router, switch them to ports 3 & 4. If the problem continues with those same 2 computes and not with the other 2, then it's station related. If the problem moves to the other 2 computers, then it's the router.

We've swapped two comps around, and the problem stayed with computer no matter which port it was plugged in. I've also tried reinstalling XP and getting new drivers for LAN card.

You have pretty much eliminated everything but the nic's themselves.

If you moved them and it followed the pc then its not the router itself . Also make sure the speed and duplex on the nic settings themselves is auto for speed and duplex as this is all these cheap home routers know otherwise you will have a speed/duplex mismatch which causes errors and slow response.