Yeah, you can rejoin them, but in the meantime I would catch some crap from other Admin wannabes for removing valid machines in the first place.

Unfortunately we have run a Wild Wild West type of Admin on our systems for a long time. The AD is now much tighter, but our NT Domain is not that way.