I think Google legally had a mechanism to do this, but ethically is messed up big time. The saying was "don't be evil", not "don't be criminal". I don't know if Google leadership was evil but the underlying principle is that "don't be illegal" is a low bar. I expect everyone to strive to do much better than that.
I don't see a lot of calls in these comment threads for an employee bill of rights or something, so I don't know why this keeps coming up.
Ultimately employment comes down to a voluntary contract between the employer and the employee. Personally I don't feel that it is the responsibility of the government to dictate what those contracts look like.
Generally the thought is that laws correspond to morality. Anyone who has taken one look at some knows this is not the case, but that may be where the link between "don't be evil" and "don't be criminal" come in to play.
On that note, I don't think the memo was intended to speak for Google, but rather _to_ Google. Was it even intentionally public? Or was it leaked?