2.6.18 is probably to be considered as old (> 2 years).
I have 2.6.27.19 on my machine
(openSUSE 11.1 on a GA-EX58-UD5)
and ran into similar problems.

Linux installed the r8169 driver which enabled networking
initially.

After some time (first reboot?) the network disappeared
and could not be found even in the BIOS.
Since I had fiddled around with the network settings,
I tried to rescue the system and then a reinstall which
still did not work.
Pulling the plug for one minute, like someone suggested
elsewhere worked.

I then checked the source and discovered no support for the chip
so I found the latest driver from Realtek and built the module
and installed it.
Still did not work, so then I removed the r8169 driver
which was also loaded, and then finally I was OK.
Have been running for one day now.

I think you should recheck the Realtek website, since
the driver was really new.

BR
Ulf

Gigabyte EX58-UD5
 

I had similar problems with the Gigabyte EX58-UD5 and an Intel core i7 960 running RHEL5.3 kernel 2.6.18-128.1.1.el5 This motherboard has dual onboard LAN controllers based on the Realtek 8111D chip. I couldn't get ethtool to change parameters to match my WAN link so I had to disable in the BIOS. Installed an old Intel based PCI LAN card and this worked fine. Still having problems getting my programs to load smoothly though?

I added my r8168 to modprobe.conf and this has helped sustain a reboot :) However. my second PCI card isn't seen by lspci :(

I wonder when Gigabyte will fix the BIOS, to stop the onbard ethernet device preventing the PCI ethernet from being detected correctly?

Works fine
 

The following runs great (no problems within a month) on ubuntu 8.10:

p6t deluxe
i7 920
9600gt

Thank you all! =)