You should notice the context of the verse you quote (Deuteronomy 30:11), because it comes after this:
These are the words of the covenant, which the Lord commanded Moses to make with the children of Israel in the land of Moab, beside the covenant which he made with them in Horeb. (Deut 29:1, KJV; or "in addition to the covenant which...etc", NIV).
From chapter 29 to the end of Deuteronomy we have a Covenant besides the Covenant made at Horeb/Sinai. The Covenant given at Horeb was the Covenant of Works. So these chapters relate to the Covenant of Grace.
This will be mostly on Deut 30:11-14 and Romans 10:1-13.
Where Paul says "as touching the righteousness which is in the law, faultless" (Phil 3:6) he can only mean that his reputation amongst his fellow Pharisees was faultless based on their (and his) very shallow understanding of God's law, (including that it only required an external obedience). He wasn't in the least behind any of the other Pharisees in his reputation of godliness. But he does not mean he was faultless, but rather that at the time he was a Pharisee he felt himself to be faultless.
"Did the OT Israelites for over 1,000 years go through the same sense of guilt, frustration, and inability to keep the Law as did Paul (cf. Romans 7), because of absence of the indwelling Spirit?"
No, most of them didn't give a fig what God's Law said because they were proud, stiff-necked, and rebellious. Those who did care to please God suffered guilt, frustration and inability until they came to put faith in the coming Messiah and to understand the way of salvation that their good God's gracious giving of the Law implied (see below). Though I'm not sure Paul is talking about gross sinful failure before his conversion, he is perhaps rather talking about the inner failures of a fallen nature after his conversion, which can only produce guilt when a saint loses sight of the free grace of God, that he is no longer under law but under grace, but certainly produces quite a lot (bucket loads) of frustration and sense of inability so that he "growns who will deliver me from this body of death"?... growns inwardly as we await the redemption of our bodies (Ro 8:26,27), but which also encourages him to look away from himself to Christ his righteousness restoring comfort, pray for forgiveness, and draw nearer to God.
Now about Deut 30:11-14 and Romans 10. In summary, Paul shows from this passage of Deuteronomy 30:11-14 that God gave to His people a blessed law, a law which had been kept already by another, that is the coming Messiah was going to keep it for them, and therefore salvation was never going to be by obedience to the moral law but by faith in Christ.
Paul is saying this is the intended meaning of Moses, or at least, this is the intended meaning of the Holy Spirit when He gave these words to Moses.
Read the whole of Deut 30 and Romans 10:1-13. One thing to observe is that Paul makes a distinction between what Moses wrote (Ro 10:5) and what Moses said (Ro 10:6) (which is obvously itself written down else we wouldn't know what he said(!)). What he wrote is the law from God, the Law of Moses, the Covenant of Works; what he said is maybe sometimes a gracious interpretation of God's intended meaning in giving the written word, viz the Covenant of Grace.
I give a flow chart to explain Romans 10:5-10 with some prior premises and some questions, because I think that is as clear as I can make it. Remember, Paul is saying that his interpretation of Deut 30:11-14 is the intended meaning in the original, probably by Moses, but certainly by the Holy Spirit:
(Prior) Premise 1: God is good.
(Prior) Premise 2: God has chosen a people to be his people.
(Prior) Premise 3: God is good towards his people.
Premise 4: God has given as a gift to his people his Law, the Law of Moses, which is the whole moral law. (They do not have to go searching for it either up into heaven or across the sea because it has been brought near to them as a gift: this is critical to the whole argument, read Deut 30:11-14 and make sure you see it: the Law of Moses has been given by God as a gift to his people. (This critical insight was gained from "Commentary on the New Testament Use of the Old Testament", Editors: G.K. Beale and D.A. Carson).
Premise 5: The Law of Moses (which is the whole moral law) brings a curse if it is not kept, but a blessing if it is kept (see earlier in Deut 30). This is referred to in Romans 10:5 "The man who does those things shall live by them."
Question 1: Did God give to his people a cursed gift?
If your answer is "Yes" then go back to Premise 1 and start reading again (if you keep saying "yes" then you are left in a continuous loop);
If your answer is "No" (because he could not have done because of premises 1-3) then continue with:
Question 2: So can his people keep his moral law? i.e. do they have a righteousness sufficient to keep the Law of Moses, the whole moral law?
If your answer is YES: then google search "Say not in your heart deuteronomy" and you will find:
Do not say in your heart, after the Lord your God has thrust them out before you, ‘It is because of my righteousness that the Lord has brought me in to possess this land,’ whereas it is because of the wickedness of these nations that the Lord is driving them out before you. Not because of your righteousness or the uprightness of your heart are you going in to possess their land, but because of the wickedness of these nations the Lord your God is driving them out from before you, and that he may confirm the word that the Lord swore to your fathers, to Abraham, to Isaac, and to Jacob.
Know, therefore, that the Lord your God is not giving you this good land to possess because of your righteousness, for you are a stubborn people. (Deuteronomy 9:4-6)
This is the passage that Paul is elliptically refering to at the beginning of Romans 10:6 "But the righteousness of faith begins in this way "Do not say in your heart"...etc. The one speaking in faith begins by affirming the soul has insufficient righteousness of itself.
If your answer was YES to question 2 ("So can His people keep His moral law?") then go back to Question 2 and start reading this post from there again and down. (You are again caught in a continuous loop.)
If your answer was NO then continue:
Question 3: Can the law be kept?
If your answer is NO then you are saying it was given as a cursed gift; go back to Premise 1 and start reading all again. You are again in a continuous loop.
If your answer is "YES, but it could not have been by the recipients", then you are saying in summary:
God has given to his people the gift of his commandment (Deut 30:11), the Law of Moses, which is the whole moral law; (his people do not have to go looking in impossible places to try to find it); this gift that God gave is a good blessed gift; but we cannot obey it and therefore for it to be a blessed gift then the commandment/Law must be given as a fully perfectly obeyed commandment, kept by someone else on behalf of God's people. The Law of Moses can be considered to be already obeyed at the time it was given, by the coming Messiah on behalf of his people.
That is the first part of the meaning. Now for the second part:-
So then the whole Mosaic Law has been given as a good gift, that is a Law which has been obeyed, and it can only be understood as such by those who agree with Deut 9:4-6 and thus acknowledge they cannot keep it themselves; and who receive it as good gift by faith, believing it is kept already for them.
Those who receive it in this manner now know they have an imputed righteousness, a righteousness they haven't worked for but received as a gift.
The question now becomes "Where is this gift, this righteousness?" The answer is this righteousness came down from heaven, and rose from the dead, in the person of the Son of God, and is now in your heart and on your lips.
So a Perfectly Obeyed Law is given to them as a gift, which is the same as the gift of an imputed righteousness.
For this commandment that I command you today is not too hard for you, neither is it far off. (Deut 30:11)
The Messiah has not yet come, but all that he will do has been promised by God, and the promises of God are all as good as done already, therefore you must see it as a law which is an Already Perfectly Kept Law, and therefore this Law is not too hard for you or too distant from you;