I did an "experiment" with my phone (Samsung Nexus S, Android 2.3):
Settings --> Date & Time --> Automatic --> OFF
Then I manually set the time to a wrong value (real time + 5 minutes).
I switched the phone off. With off I mean really off, not standby, the status when the alarm does not work.
After a few minutes I turned it on again.
The time displayed was still the wrong value I set before, i.e. the updated current real time + 5 minutes.
This means that the phone should have an internal clock that works even when it is off. In reality it may not have one, but it should store the delta between the current time obtained from the network and the time I set; however this seems to be quite unrealistic.
So, this makes me think that Android phones have an internal clock with its own battery, and this should be able to make the phone boot at the appropriate time.
Could be something missing in the Android OS itself?
P.S.:
Does anyone know if it it possible to make the phone wake up at a specific time? If it was, we just should make it boot five minutes before the alarm is set...