To add to @ErikA answer. There are two DNS changes that are made with Google Apps.
Domain Verification, which is the
googleXXXXXXX.yourdomain.com you
mention. This is done to confirm you
are the owner of the domain, and
should point to google.com.
EXAMPLE: googleXXXXXXX.yourdomain.com => google.com
Mail, and all other apps like chat,
docs, calendar etc should have a
CNAME, which point to
ghs.google.com. It is not a
website, therefor not responding to
HTTP requests.
EXAMPLE: mail => ghs.google.com
To recover the googleXXXXXXX address you should just have to go to the Google Apps admin as the service should have detected the dropped validation and ask you to re-validate. You can submit the re-validation here: http://www.google.com/a/YOURDOMAIN.COM/VerifyOwnership, placing your domain in the proper spot.
The 2nd CNAMES you can just recreate as the destination is always the ghs.google.com and the pointer can be whatever you like. Just make sure they match the URL settings in the Google Apps admin.