If one is to believe the source of your previous info, then you'd be
absolutely right - and that's why the system isn't designed to work that
way.  It's amazing how wrong a CSR can be with just a little bit of the
truth.  The larger truth is, yes, when one powers up a phone, the boot
process includes re-sourcing network selection - forcing the phone to
re-register - which can be helpful if the "system" has lost track due to
some technical snafu.  Wireless providers have a huge investment in
equipment and processes that deal with which system any particular phone
is registered with at a given moment - is he home? or roaming somewhere
"out there"? - and stuff happens (not that there's any surprises with
that).  A subscriber's voice mail system is the same system regardless
of where the phone is, unless the subscriber's account was shifted to a
new system during the night, aka. stuff happening.  If that subscriber
was roaming while their voice mail system was upgraded, some incredible
screwball thing may have happened despite best efforts to avoid the
screwball events.  As I said, Cingular's efforts to deal with their
acquisition of ATTWS customers is ongoing, and this includes shifting
subscribers around amongst numerous voice mail systems.  So, clearly,
it's one thing to have a message deposited, quite another to notify the
subscriber of that event.  Aside from temporal shifts in the earth's
wobbly orbit, I think Cingular's efforts, though not perfect, are
significantly on track.  For those of us that are "hanging in there",
the dust will continue a while longer during Cingular's own shift from
blue to orange.

No, I'm not employed by Cingular, but friends of mine are, hence the
source of my information, generally while bending an elbow or two.