Well, many did. Like David who said that blessed was the man to whom God would not impute sin. And then also said that the Mosaic law was his delight meditating in it day and night. In my observation the law was a real zinger for those who were saved because even tho salvation never comes thru law but by grace alone, God always has a rule of life for the saved and for them it was an undoable request of keeping the law of Moses. That as well as not having a permanent indwelling of the very Spirit of God is so very different from who we are today as members of the Body of Christ.
Here is how I understand the topic (if you disagree you are probably right, I'm not the sharpest tool in the shed. But it is how I see it).
There are a lot of things to consider. I do not think that we can accurately compare David’s experience to that of Nicodemus (and 1st century Jewish thought) because Jewish thought was not the same. David held a religion that was, by the first century, divided among extremes. The Sadducees held a faith centered on the Temple, believing that the Temple is where the Law belonged and was accomplished. The Pharisees held a faith centered on the people (on Israel) believing that the Law belonged to the people and that was where it would be accomplished. The first century Jewish concern was how Israel would be in a right standing with the covenant they inherited by birth. So the Law was not a means to obtain salvation (they believed they were born within the Covenant) but rather one’s standing, and Israel’s standing as a whole, within that Covenant.
In this way we are looking at a remnant theology, not a theology centered on obtaining salvation but a theology of inclusion. Jesus’ words to Nicodemus places the religion of the Sadducees and the Pharisee’s outside of the kingdom of God. To be righteous, or right with God’s covenant with Abraham (not the Law but the Promise) one must be reborn. This means what Nicodemus held was obsolete. He could never see the kingdom of God on his current path. God’s righteousness was being manifested apart from the Law, not through it.
I absolutely agree with your use of David and Mary, though. Not for their religious views but because of the activity of the Spirit. This is something I believe Nicodemus did not understand, but would come to understand through the Spirit (I say this based on his actions later on in Scripture).