My problem with the last part of your post is that many (most?) religions have their own versions of creation. My experience is mostly with the various Christian faiths, so my responses are mostly related to them.
The bible does say God created man in his image. Evolution says humans evolved from other forms of life, through common decent/selection. These two views, the Biblical and the scientific, are opposite views. I do not believe the the Biblical statement. Many religious people do not believe the Biblical statement. That does not remove the fact that the book that many religious people base their faith on states that their God created man in his image.
Do you agree or disagree that taken at face value, the Bible contradicts science, and thus crosses the line that NOMA alleges exist? My point being that if it does how can NOMA be a valid principle in the case of Christianity? Since the largest group of religious people in the USA claim some form of Christianity as their religion, how can we say there is no overlap between science and religion? We may disagree with the interpretation of the Bible by these Christians, and I certainly disagree that any God exist, let alone created us, but that doesn't change the fact that the Bible makes a claim that directly conflicts with science. I'm sure there are similar examples of conflicts with many other religions (I can provide links to creationist Muslim sites if that would help

).
We may feel that there is no conflict, but when the basis on which a religion is founded indicates a conflict, how can we say the practitioners are in violation of NOMA, when they are following the guidelines/information laid out by the creators of the religion? I contend that it is the religion that crossed the line at it's inception, and that, IMHO, invalidates the idea of NOMA. The line between religion and science was already crossed before what we, today, know as science existed.