Suppose I register a new domain name with Godaddy.com, and receive
name server information with my registration, and then I change my
name server information within 2 hours of the registration.  How
likely is DNS propagation to have finished after 24 hours, and when
can I be sure that DNS propagation is complete?  I believe it is up to
24 hours for new domains, and up to 72 hours for existing domains. 
Would the fact that it is so recently shorten the likely period of DNS
propagation?

A second, related question - can email sent during the propagation be
lost forever, or will it either eventually find its way to the
recipient, or else return to the sender?

i am not sure i can tell you for sure when propagation is "completely
finished", however, in the past 1 or 2 years, the propagation seems to
have sped up quite a bit. none of my renewals or new registrations
through godaddy (around 30 com, net, org, info and us domains) took
longer than 9-10 hours max. most already were set to go after no more
than an hour or two. so i would figure that, even if you are taking
conservative numbers and double this time, 24 hours is a pretty safe
bet to assume that the domain is all set.

as for the emails: they will NOT be lost forever. even after the
propagation is complete, as long as your account is still set up on
the "old" server, you can fetch the email from there by entering the
servers IP address as POP server. just do this once, after your domain
is changed and you are all set. an alternative would also be to get a
free email account - gmail would be pretty handy, since it offers pop
mail for free - and set up an email forwarder to this address on the
"old" server. as long as the emails are being routed to this old
server, the emails will end up in the gmail and be easy for you to
get.

hope i could help!
sid

It depends on the TTL of the host listed in DNS. See this post for
more information:

http://www.mattcutts.com/blog/moving-to-a-new-web-host/

1) DNS propogation needs atleast 72 hours but depends on region to
region like us, europe, asia pacific and rest and goes orderly as
indicated.
2) Yes email sent will lost and won't be returned to the sender as the
mails will be in loop and will return to the sender... during
propagation if the earlier domain is still not receiving it. Thats Y
it is very much advised that let the earlier and present domain
receives the mail till all the mail start coming on the new domain or
72 hrs. are being spent. I have been into this type of problem earlier
but following what i said above i didn't lost a single mail.

cheers!!!