mine does that problem with 3 batteries...

after some tries it boot... sometimes 2 sometimes 10...

reinstalled power kernel nothing changed

you could try using flasher booting from ubuntu with u-boot. Copy the flasher binary from maemo to an external location, boot ubuntu, copy flasher to /usr/bin, download images and try flashing (haven't tried it but it should work)

After seeing the gcc-4.6 thread, I'm thinking this is the reason my phone doesn't successfully reboot on it's own any more.

http://talk.maemo.org/showthread.php?t=81861

Thank you all for all your answers.
I guess I did forget to mention I was using kernel-power 50. I did a kernel reflash, as sugested, and I must say the problem goes away almost completely by that - it will only fail to boot when REbooting (there's a tutorial somewhere about how to re-activate this option in the power button menu).
Obviously after the kernel reflash I am left with a bunch of packages that are installed but aren't used ( kernel-power* ), so I purged them and re-installed kernel-power-flasher (which brings with it kernel-power and kernel-power-modules).
And about 5-10 normal shutdown/startups later I can say with some confidence that it is cured.
However, what brings back the issue is installing kernel-power-settings and batterypatch (not sure yet which exactly is the culprit). And that's a shame 'cause I like the idea behind batterypatch.
Yes, I did try a bunch of different batteries (four of them, to be exact). Problem replicated with each of them.
As I said before, I've seen no corellation between taking the battery out and boot up success rates. Keeping the phone turned off (with battery in it) for that same hour might have the same results for all I know (didn't do any specific testing on that, but at least the phone time wouldn't reset). Let me know if you try
In theory the n900 should be able to flash itself (meaning flash from the device, without using any external computer). In fact, that's exactly what happens when installing kernel-power-flasher or restoring a backup with backupmenu - the device is flashing an image (be it just kernel or entire eMMC) into itself.
If you are able to boot the phone, at least occasionally, it might be worth a try using backupmenu. I've read somewhere that the backup images it uses are compatible with the nokia's flasher, so I'm guessing the reverse is also true. In that case one should be able to install backupmenu, put the firmware image (vanilla or combined) on an SD card and restore it to the device from within backupmenu.
I will try it on my old n900 (also broken off USB). Will report back when I have results.

Sometimes I need a second try to successfuly boot..after flashing it's good but with time it starts to happen. Maybe it's just "normal" thing..I don't know. Good luck!

Powering off the phone for an hour is not the same as pulling the battery for an hour. Pulling the battery resets some settings and brings you to the localization config menu once the phone comes up. I also have to change the time format from 12-hr to 24-hr each time -- so pulling the battery does seem to cause the phone to loose some settings.

If there's another/better way to reset the nvram (correct term for the n900?), then that should work too.

My n900 has the exact problem. I've tried many ways to solve it without any success. So finally,I just live with it.

Are you kidding?

I am sure if you test individually you will work out which one.

i also had same problem....once i flashed my phone but the problem nt gone.....but few days ago when i reflashed my phone.......completly means rootfs and EMMC both...then now the problem is solved...hope it works for you.....