Yes No-CD/DVD Patches are legal.
I note everyone so far in this thread is in a different country, which makes the definitive answers to this question somewhat amusing.
As far as I know (and this is
not legal advice) these patches are not legal in the United States. The CD check is a copy protection technology, and the Digital Millennium Copyright Act makes it an arguably criminal act to subvert it, for either the author or the consumer of the patch.
I also seem to recall that Australia passed a similar law to the US DMCA a few years ago, but I couldn't even begin to advise you on what differences, if any, might exist.
The best advice I can give you is, first, consult a local attorney with experience in this area, but second, if you're sufficiently worried about the legality of something that you'd need to consult an attorney, you're probably better off just not doing it.
As a final disclaimer, I am in no way saying such laws aren't stupid, just so you know, but stupidity of the law is not an affirmative defense.