Troubleshooting Random Hardware Lockups

Hello,
I am hoping someone here can point me in the right direction for troubleshooting a homebuilt PC that's having random lockups. I've wiped and reformatted twice, so I'm sure it's not a software issue. I'm also sure that it's not a compatibility issue as this PC is going on 5 years now and it's been running great until recently. Started locking up randomly, I don't get any video pixelation, it just stops completely. Weird thing is, when it does, it takes down the internet for my other two PCs on the network (Verizon FIOS, others hook through router, not through this PC).
Sometimes it happens when I first start the computer up, sometimes it can run for days fine. It is not recreatable in any pattern I've seen. Checking every event log available in Win 7 gives me squat, nothing is registering any issues prior to lockup.
I tried replacing the power supply, and for about a week it seemed to be fine. Then it started up again full force. I've held off on the most recent windows updates (from the last few weeks only) just in case that was the issue, but still doing it. I've also checked the heat and it's running normal there too.
Here's my setup (using onboard sound and NIC:
Win 7 64-bit
ASUS MAXIMUS FORMULA LGA 775 Intel X38 ATX Intel Motherboard
Intel Core 2 Quad Q6700 Kentsfield 2.66GHz LGA 775 95W Quad-Core Processor BX80562Q6700
G.SKILL 4GB (2 x 2GB) 240-Pin DDR2 SDRAM DDR2 1066 (PC2 8500) Dual Channel Kit Desktop Memory Model F2-8500CL5D-
Seagate Barracuda 7200.10 ST3250310AS 250GB 7200 RPM SATA 3.0Gb/s 3.5" Internal Hard Drive -Bare Drive
EVGA 012-P3-1470-AR GeForce GTX 470 (Fermi) 1280MB 320-bit GDDR5 PCI Express 2.0 x16
CORSAIR Enthusiast Series TX750 V2 750W ATX12V v2.31/ EPS12V v2.92 80 PLUS BRONZE Certified Active PFC High