Okay, this is the weirdest problem I've ever hard with computers. Here's what happened:

1. I had a few years old Pentium D 2,8GHz processor running on Asus P5VDC-X mobo. PQI 566MHz DDR2 and GF 7600GS 256mb PCI-E, 350W power.
2. I updated the mobo to Asus P5L-MX to support faster PCI-E cards. Everything worked fine, despite the processor ran too hot (58C on high use)
3. Because of the overheating I replaced the thermal paste but it had no effect on the temperature.
4. I thought I used too much paste so I replaced the paste again.
---
5. Bang, no video when I turn on the computer. I tried taking off everything part by part but nothing worked. It didn't work even when I only had processor and used the integrated graphics port. Tried resetting the bios too.
6. Nothing worked so I put back the old P5VDC-X and it worked like charm.
7. I thought it was logical that the problem was caused because of the mobo so I bought a new one, Asrock G31M-S.
8. No video... Did the same steps to this one too. It also had integrated gfx but it didn't work either.
9. The old P5VDC-X still works.

So I have no idea what's causing the problem. Is it the CPU? Mobo? PSU? RAM? I have no speaker on my case so I can't hear any beeps, but it won't start loading the OS from the hardrive and my USB mouse won't turn on. Tried using a differen't monitor too.

The main point is why it stopped working suddenly on new mobo's but still works with the old P5VDC-X? Any ideas? Let me know if I forgot to mention something important.

Two new motherboards tells us you made the same simple install error in both of them.
Tell us more about power supply, memory, cable.
Did you make sure the memory was correct for both new boards, and what is the memory on the old board. Would also like to know the power supply and other hard ware.
What happens with the most basic, simple install. Does everything light up?

If you used the same hard drive with the same Windows install on the two motherboards, that is the problem. Windows has detected that you have changed the motherboard and will not operate unless you reinstall Windows on the drive on each new motherboard... One install for each motherboard.
My guess is that you will be fine if you change hard drives or do reinstalls or repair installs of the Windows on the new motherboard.

Thanks for the input.

You suggested it was a simple install error so I tried installing the P5L-MX once again. It worked. Thanks a bunch for pointing me to the right direction because otherwise I would have bought a new CPU to see if it would have fixed the problem. Some components probably didn't get in touch well enough, even thoguh I tried reinstalling every component earlier one by one.

Anyways, now it's working. Thank you!