I noticed the exact same thing . When the power is off sometimes it doesn't ring or pop up calendar notices, and then when I turn it on I get simultaneous "missed call" and "voicemail" alarms. It shows the current timestamp for the missed call - even though I know it's old. The strange thing is that it doesn't happen all the time. Sometimes it comes on and rings - sometimes it doesnt. I thought I'd wait for a new software version to come out - I got the latest PRL this morning - 21. I've also had people complain of it ringing 10 or 11 times before I answer it - when I know I've answered it quickly. (not sure how that happened without going to voicemail - but maybe that's a solution to increase the number of rings before going to voicemail?)
I noticed on another post that someone installed wizbar - and was getting the same problem. I originally installed wizbar because I loved it on my iPaq, but have since done a hard reset and not reinstalled. I'm not sure if that could leave something on the phone through a hard reset or not?
I bought the three year replacement plan - and am tempted to get another one to see if it has the same problems. . .