It depends on the NCA Kevin. There will be a withdrawal order and that will tell you the extent of the withdrawal. The typical mineral withdrawal will say
withdrawn from location, entry, and patent under the mining laws
That means exactly what it says in land status speak:
location = mining claims
entry = application for patent
patent = fee grant ("Title") to the land under the mining acts
When it is written that way there is no restriction on prospecting itself.
I've read quite a few of the thousands of withdrawal orders and that is the usual language with some small variation. Rarely is prospecting included in a withdrawal order but it does happen sometimes. You need to look up and read the original.
I see in Colorado you have three NCAs. You will find the text of the withdrawal within the Congressional Acts that created them.
For the Gunnison Gorge NCA
Public Law 106-76
For the Dominguez-Escalante NCA Omnibus Public Land Management Act of 2009
Public Law 111–11 (PDF)
For the McInnis Canyons (formerly Colorado Canyons) NCA
Public Law 106-353
A quick check of those laws show that prospecting is not spelled out in any of the withdrawals. Being that they are NCAs the Secretary of the Interior is allowed to make management orders about land use. I doubt the Interior Secretary has specifically restricted prospecting but knowing how the local chotas in the Gunnison like to make up their own rules to suit themselves it might be a good idea to check the Federal Register to see if their boss did such a thing. The law does not permit local land managers to make up their own rules but try explaining that to a guy in a poorly made green suit with an iron on "badge".
There are 16 National Conservation Areas. All of them are in 7 western states. Each was enacted by Congress. Each are governed by the law Congress wrote creating them. Each law is similiar but different so there is no general law affecting all NCAs.
Although there may be other "Conservation" areas they are not federal NCAs and they were not created by Congress. Being as there are no public lands or NCAs in Missouri you are probably dealing with a State or County organization there Russ. Short of getting the law changed or a two by four judiciously applied you are pretty much SOL east of the Mississippi.
On the issue of prospecting and withdrawals. The Congress has consistently supported the idea that even in areas closed to mining claims there is still a need to investigate the extent and type of mineralization by prospecting. Congress specifically allowed prospecting in the Wilderness Act and even in many areas that are protected by various designations it is still permitted to prospect. The whole tone of most land laws incorporates an abiding respect of mineral ownership by the people.
There is a principle of law that states "Nulla poena sine lege" which is Latin for "no penalty without a law". It's the job of the badge telling you something isn't legal to pony up with a law that states it isn't legal - they need to be able to point to the law that allows them to act. Without a written law to back them up they have nothing they can charge you with that will stick. Writing "I don't like this guy" on the ticket always results in a win for the miner. I deal with land management agencies a lot and in most cases when they are pressed for their legal authority to do something they come up with zippity do-dah. The wise prospector will find out what the law is before they prospect so they won't be caught out with nothing but "I read it on the internet" which is the civilian equivalent of the land manager's "cause I said so".
In real life the land manager probably doesn't have a clue that they can't just make stuff up or just rely on their own interpretation of something they think they read. You see the idea that they can promoted everywhere - even on this forum. The law of the land is that the law, and the enforcement of the law, is uniform everywhere. Local land managers don't get to make up their own version of the law. This is the essence of "due process" that you hear so much about but never were told what it means. When someone tells me "we do it different here" I know and smell BS.
Rarely is it wise to challenge an aggressive low paid idiot with a gun. Life experience will explain that sometimes it's necessary to do so. I remember an encounter I had a few years ago where several federal morons with guns and iron on badges were threatening to shoot my livestock. Eventually I was able to explain to them the mathematics and probable outcome since they were outgunned and out of line - the local Sheriff was a great help in conveying the reality of their situation. They did back down and move on but without the very real threat of grievous bodily harm they didn't really care that they were out of line and out of their jurisdiction. They felt macho bluster and threats would rule the day as it had before for them. I distinctly remember the stupidest of them constantly loudly repeating "I'm a federal agent and I can shoot anyone I want" as if repeating nonsense would make it a fact. Choose your battles wisely and remember that being right and jailed or dead is a pitiful version of "victory".
Prospect wisely and prospect well.
Heavy Pans