Keeping secrets in the Federation
All the information we have from the Prime Star Trek Timeline as far as Section 31 is concerned, was nebulous and mysterious, and left intentionally so, reducing the ability of anyone attempting to find or infiltrate the organization. (It also amped up the curiosity of the viewers, who up to this point had no information about a covert arm of the Federation.)
It was implied that Section 31 had a limited connection to Star Fleet, so it was easier to perform missions the Federation might prefer to stay "off the books." While it is certain impressive to say there are no records, it would be almost impossible for this to be completely true given the level of complexity in the Federation and the galaxy at large.
The claim was nothing was ever written down or able to be found out about the organization. Granted, given the computing power of the Federation, it might seem possible that such a secret could not be kept hidden but the first rule of information management applies. "If you don't want people to know about it, don't connect it to the internet or other public information systems."
In the Prime Universe, it was highly likely Section 31 maintained no facilities that could not be moved and never connected its resources to any public networks. It is possible many of their command centers could simply be on ships that never settled in any place for a significant amount of time.
A starship could function as both a barracks, a training center and a research facility if sufficient resources were allocated to the task. A starship could also be completely destroyed via autodestruct if such information were about to fall into enemy hands. They likely used powerful or even illegal (by Federation standards) encryption techniques or alien technologies ensuring even greater difficulty in decoding their resources if discovered.
Space is very large, it is likely if the Federation wanted to keep an agency such as Section 31 hidden, it had the resources, the capacity and the ability to do so. While this may tarnish the reputation of the Federation as a "good government" I believe the writers understood that even good governments have espionage and covert operation needs, if for no other reason than because other governments might use them against them.
Realistically in either the Prime Universe or the new Abrams-verse Star Trek:
No shadow organization, especially one working in the shadow of an organization as large as StarFleet could possible work without having an operational center, a limited command structure and a resource profile (where they get their tech, goods, tools and services to run their operations). In such an organization, there are likely to be agents and operatives who work for both organizations (StarFleet and Section 31) whose capacities are known only to an elite and select few.
Being a shadow organization means they are unofficially involved in whatever is necessary to be done when official channels cannot do the job. Sometimes that may mean espionage, specific applications of force, subversion, or sabotage. These operations require both trained personnel, advanced equipment and a place to develop such resources. On our Earth, they might be called a "skunkworks", where new technologies are designed, tested, developed and/or deployed.
The Federation Library which housed the Section 31 skunkworks, while unorthodox, is a reasonable working idea. Hiding your skunkworks in the center of your most heavily defended areas (meaning on Earth, in the heart of the Federation) is an option if you are developing technology you want to keep both secret, yet accessible. The downside is, if someone knows about it, they can harm both your facility and morale by attacking you there.
Saying you have a super-secret, completely untraceable organization, so secret the government barely knows you exist sounds great for a recruiting pitch, but once you consider the logistics of such an organization, it is much easier to say than it is to do.
Production Notes on Section 31
From Memory Alpha:
Sloan and Section 31 epitomize Deep Space 9's vision of a more realistic universe in which "paradise" has started to crumble and where the Federation struggles to maintain its high ideals amid difficult situations.
Section 31, along with its morally questionable actions, is one of the elements that have made DS9 highly controversial among Star Trek fans; the other being the introduction of the Maquis and Sisko's infamous speech to major Kira about how easy it is to be "a saint in paradise". (DS9: "The Maquis, Part II")
As Ira Steven Behr said: "We need to dig deeper and find out what, indeed, life is like in the twenty-fourth century. Is it this paradise, or are there, as Harold Pinter said, "Weasels under the coffee table." Sisko's speech in this episode - ("The Maquis, Part II") - was the beginning of our really starting to question some of the basic tenets of Star Trek philosophy." (Star Trek: Deep Space Nine Companion). The introduction of a somewhat darker and less optimistic side to the Trek universe culminated in the creation of Section 31.
While Sloan appeared to bear the rank of a Fleet Captain while posing as an officer with Starfleet Internal Affairs, it is possible that he truly did hold this rank. Furthermore, Section 31 may have existed under the umbrella of Internal Affairs, at least, unofficially, especially since Dr. Bashir had concluded that the virus was introduced to Odo by Section 31 when Odo was on Earth, at Starfleet Headquarters.