Just make sure that when/if you copy over the staging site to the live domain that you don't copy over the robots.txt, htaccess, or whatever means you use to block that site from being indexed and thus have your shiny new site be blocked.

Here's how I dealt with a similar situation in the past.

Robots.txt on each of the dev subdomains and on the live domain. Dev subdomains robots.txt excluded the entire subdomain, and subdomains were verified in GWT and removed as needed.

Made live subdomain robots.txt read-only so it didn't get overwritten. Should have made dev subdomains robots.txt read-only as well, since they sometimes got refreshed with the live content (there was a UGC database that would occasionally get copied to a dev subdomain, and we'd have robots.txt get copied over too and dev subdomain indexed).

Set up a code monitor that checks the contents of all of the robots.txt daily and sends me an email if anything is changed.

Not perfect, but I was at least able to catch changes soon after they happened, and prevented a few changes.

That's an interesting one. I'd email that to the help desk at help@seomoz.org to let them know about it. If there's some kind of cause of it that would be helpful for others to know, it'd be great if you could post more information back on this thread.

Have you checked the response code of your custom 404 page and made sure that it's returning a 404 and not a 200?

It's often an internal link that's a bit screwed up that will cause this to happen. Look for a missing colon in http:, or something like that.