I don't think it is propagated. You have to go change  their name
everywhere it is used.

Correct. We had that problem  a few times and had to (ahem) modify the
database - which, I have to immediately note, is an unsupported action
by Microsoft. If you need the SQL statements, contact me off-list.

The Account Synchronization feature of DeliverPoint will update the User
Info.

Nooo don't do this!

Everytime a user  visits a site in a site collection,
SharePoint 'caches' the user info. This saves a lot of trips to the AD.
When you change  the surname of a user in the AD, the change will
propagate to the profiles, but you won't see the change in the sites.
You will have to go to the "All People" page of the site collection and
DELETE the entry for the specific user; this is the cached user info.
Upon next visit of the user, SharePoint will notice that the info  of
the user is not in the cache and retrieve fresh data, including the
changes.

Well, but there's a problem  of scale with that solution - if someone
is a member of enough sites, this becomes fairly cumbersome to do for
each..and..every...single...site.... It also puts the burden on the
site admins rather than the system admins to do the updates (which, I
suppose you may be correct, that may be where such a thing belongs,
unless - as in our case - the update request is sent to the help
desk).

Correct me if I'm wrong - if you force an update that way, don't you
also lose any document modification information  that's associated with
that user's account? I know that when my account got screwed up
recently, all my document data got reverted to a user  rather
innocently labeled "Person".

Note the difference with sites  and Site collections. A site
collection can hold a lot of subsites, which don't cache the user
info each.
In SPS 2003, and likely 2007 as wel, user  info is tracked primarily
by its SID (AD security id), user account and/or email adress
(the "alias" fields). The account itself is not deleted, just cached
info (the All People list is actually a "this-user-visited-this-site-
collection list).
The SID remains the same (if you didn't delete and recreate the
account in AD), and thus you don't loose all document modification
info.
Fingers crossed, because I don't know if changing the email address
may have side-effects.

If you meant sites that are created in a Managed path (eg /sites/),
then yes, you will have to go by the site root site of every site
collection this user has visited...

I describe this scenario in a couple of different posts for V2 (Still
applies to V3)

I'm not updating  SPUserUtil for V3, but rather we're working on a
similar feature in DeliverPoint

Handling Login Name Changes

blogs.msdn.com/.../688571.aspx

Synchronizing Display Names and Email Addresses

blogs.msdn.com/.../691488.aspx