I've been battling with this board all week, and even though I was able to solve my problem, I might as well document it in case it may help someone in the future. The story goes as follows:

An acquaintance of mine brought me his desktop PC because it stopped working (no POST). It's a socket 754 Athlon 64 3000+ on a MSI K8N Neo3 with 1GB of RAM, a PCIe 128MB Radeon X300 SE, 160GB SATA HDD and XP SP3. Ruled out the video card as the culprit for the system not POSTing - dead card. Put in my good 'ol EVGA 7800GTX to check if the board was still OK and it is - works fine with the 7800. So I told him he just needed a new video card and that basically anything PCIe will do. I offered to buy the cheapest one at my nearby computer shop and replace it for him. He agreed so I went and bought a Sapphire Radeon HD5450 which was the cheapest they had in stock. Got it home, put it in, and the problems started.

It won't POST even though it runs fine with the 7800. Put in my diagnostic card, it gets stuck at POST code C1 (which seems to be RAM based). Tested the 5450 on another board in case I got a dud, nope, works fine. I upgraded the BIOS to the latest version I could find on the MSI website - no luck. So I got back to the store, whole PC in hand, and explained the situation. They tested the two other cheap cards they had in stock (a Geforce 210 and a 8400GS) and none of them worked. One of their techs told me it didn't work because the PCIe slot on the motherboard is 1.0 while the cards are 2.0 (but aren't 2.0 cards supposed to be backwards compatible with 1.0 slots?), the only way I could get it to work was with an old, used video card, and since they couldn't do anything else they gave me a refund.

The next day I went to a used computer parts dealer to get an old used video card for this PC, and I got myself a 128MB Geforce 7200GS for pretty cheap. Once again got home, installed the card... nothing! This time the board gave a long beep like there was no video card installed, so I went back there to complain, this time I brought the motherboard with me. The guy tried another 7200GS which didn't work either. He got curious so he started trying his whole stash of used video cards on the thing, various early PCIe Geforces and Quadros, some Radeons... none worked, they all stuck at C1. He then tried some AGP cards, and out of the whole lot only a 256MB Radeon 9250 worked (which didn't surprise me since the AGP slot on this board isn't really AGP). As he was running out of cards to test (and patience!), he pulled out a boxed ECS 1GB GT610 and tried it out. Success! I left that place with said GT610 and a smile of relief on my face. The PC works flawlessly with the new video card and I can finally call it a job well done.

Is the K8N Neo3 really that finicky with PCIe video cards or could it be damaged in some way? I believe the PCIe lanes are fine since the card runs in 16X mode. And what could be so special about the GT610? Either way it's working now. I hope this could save someone else from a lot of headaches if they happen to have the same issue as I did.