Hi everybody,
Thanks to you all for your replies. Now I know I'm not alone!
I've solved my problem (with a few side-effects, though).
Seems the problem comes from kernel-power50, kernel-power-settings and overclocking (whether it's done via batterypatch or qcpu or other means).
Kernel-power-settings keeps the kernel settings between restarts. Seems like useful stuff, but somehow doesn't work resulting in multiple restarts required before device finally boots. I suspect it's been broken in latest kernel-power versions but am not sure.
So, for anyone having the same problem the solution is to just uninstall kernel-power-settings (which will take with it batterypatch if that's installed).
Side effects: after each restart need to manually overclock (I keep mine at 850MHz) and activate SmartReflex. Of course another side effect is I can't use batterypatch or other software dependant on kerne-power-settings.

I would be interested to know how to automate the overclocking settings loading to take place after booting is finished. Otherwise I prefer doing it manually instead of spending ~10 minutes for each restart.

how about editing /usr/share/kernel-power-settings/default
Did you try it?

Why not follow the docs and put your settings in /home/user/.kernel ?