The CP9 of One Piece. While the CP1-8 (CP meaning Cipher Pol, or numbered police) are well-known government intelligence agencies, the ninth one is a complete secret that the ordinary citizens only think of as a rumor. This is because the CP9 has the right to kill whoever they feel is an obstruction to their mission.
James Edwards: Hey, what branch of the government do we report to?
Agent Kay: None, they ask too many questions.
The movie Conspiracy Theory features an unnamed government agency, and the way one of their agents describes it could be an excellent page quote:
"If the intelligence community is a family, think of us as the uncle no one talks about."
In Hellboy, one of Tom Manning's jobs is to deny the existence of the Bureau of Paranormal Research & Defense and cover up all evidence of their missions (which is a deviation from the original comic books, where the Bureau's existence was public knowledge). But in the sequel, Hellboy deliberately reveals the Bureau's existence by appearing on a live news broadcast.
The covert organization in all iterations of Nikita, including the twoTV series and the Trans Atlantic EquivalentPoint of No Return, is a black-ops program for assassination and counterintelligence that does not officially exist. Which has allowed the program's leader to turn it into a work-for-hire operation that the government can't shut down.
Deconstructed in Transformers when Lennox, Epps, and the other Army Rangers refuse to take orders from the Sector 7 agents because their unit does not officially exist.
In the Matt Helm series of novels written by Donald Hamilton, the U.S. assassination agency with no name that Matt works for.
The assassination agency CURE in The Destroyer novels, which was created by President John F. Kennedy to protect the U.S. by working outside the Constitution.
In Robert A. Heinlein's The Puppet Master, the narrator explains up front that you've never heard of his organization because they do not exist.
The Rainbow counter-terror unit in the Tom Clancybook and video game seriesRainbow Six. Officially all its operations were performed by special forces units loyal to the country they occurred in. Though by the later Ryanverse novel The Teeth of the Tiger, Rainbow has apparently become an Open Secret in the government.
Teeth of the Tiger introduces "The Campus", a play on this trope. Another counter-terror organization set up at the behest of President Ryan, it operates completely outside of government oversight, relying on its cover as an investment firm*
and a little help from "intercepted" CIA and NSA intel
for funding. Aside from Ryan, only a handful of people within the government are even vaguely aware there is more to The Campus than meets the eye, and the vast majority of those are mid-level types acting as "talent scouts" for the organization.
Quiller works for The Bureau, an organization directly responsible to the Prime Minister of Britain, with "powers that would be called into question in the House of Commons should its existence be revealed".
Much like the Men In Black example, Played With by the Ministry of Magic in Harry Potter. Its name suggests a governmental department on par with the Ministry of Defense and the Ministry of Justice, but no one in the U.K.'s Muggle government knows it exists other than the Prime Minister, and they certainly don't report to him, unless bursting in unannounced at irregular intervals to give him information he has no context for and can't possibly act intelligently upon counts.
Fifteen years into the project, Stargate Command remains a secret known only to cleared members of the participating militaries and the highest government officials of the 50 nations that are signatories to the Antarctic Treaty System. The latter were only read into it because there's an Ancient outpost underneath the continent. The project was supposed to go public in the third Stargate SG-1 movie, Revolution (partly because the number of people involved is in the thousands at this point, making keeping the secret increasingly difficult), but the plans for the movie were derailed by MGM's bankruptcy.
Bureau 13 of Babylon 5, an agency so secret that even its name is rarely known. The one guy that told Captain Sheridan the Bureau's name ended up dead shortly afterwards.
The RPG has another example in the Blue Berets, a secret telepath branch of Earthforce created to counter a possible insurrection of the Psi Corps. Their description starts with a denial of their existence or any possibility thereof.
Section 31 of Star Trek. Not only are they officially non-existent, their mission statement is explicitly to do everything that the Federation won't do.
The IMF (Impossible Mission Force) in Mission: Impossible. Famous for the warning given to its leader before each mission.
"If you or any member of your IM Force are caught or killed, the Secretary will disavow all knowledge of your actions."
"The Agency" in the 2000 Invisible Man TV series is an interesting variation. Due to their low budget and few personnel they had to exist mainly as a deniable floating task force for other government agencies, such as the Department of Fish & Game.
The Grey Knights Adeptus Astartes chapter in Warhammer 40,000 are a curious example, as their existence is considered an urban legend in the Imperium, and only a select few of the other Space Marine chapters (namely the Space Wolves and Blood Ravens) who are allowed to learn of their existence. In addition, they are considered the militant arm of the Ordo Malleus, making them soldiers of the Inquisition. However, anyone else who fights alongside them are either killed or mind-wiped after the war is over in order to preserve their secrecy. Only the Space Wolves have managed to escape this, primarily because there were too few Grey Knights left after the first War for armageddon, and afterwords dealing with the situation would have required calling the entire chapter to heel, something that is virtually impossible to do to a first founding chapter.
Bureau 13 in Bureau 13: Stalking the Night Fantastic. It's an undercover branch of the U.S. government dedicated to identifying and eliminating supernatural threats.
Conspiracy X. The main opponent organization for the Player Characters is a secret government agency called the National Defense Directorate AKA the Black Book.
The eponymous Delta Green was originally an official non-existent government agency. When it was disbanded, its members continued to operate covertly and illegally, becoming an unauthorized No Such Agency.
In Exterminatus Now, the protagonists manage to get away with getting a gigantic and extremely expensive secret research facility owned by their employer sucked into a dimensional portal by the fact that since it was completely off the books and officially non-existent, there's not evidence that can be used against them. Said employer has a fit when he realizes this.
The Third Echelon in the Splinter Cell series is a black ops and intelligence agency of the US government. Their existence is hidden even from the NSA, which they are technically part of.
The Corsairs in the Mass Effect universe are a branch of Alliance Marines who conduct black ops for the Alliance without official orders. Their existence is unknown even to high-ranking Alliance officers such as Shepard.
The existence of the Osean 8492nd Squadron, a.k.a. the Belkan Aggressor Squadron, in Ace Combat 5: The Unsung War is denied by the Osean government, probably because of the unsavory association with the ex-Belkan military. Comes to bite them in the ass later on, when it turns out that the 8492nd remained loyal to the Belkan government the whole time. The Ghosts of Razgriz themselves become this retroactively, since their involvement in the war and even existence is denied by Osea for ten years thereafter—even the title of the game refers to this.
Section 8: Prejudice introduces a unit called the Spear which serves as the game's Big Bad. It was an elite paramilitary unit intended to exterminate any alien life that could be an obstacle to human colonies (read: all of it), but its leadership began to get mentally unstable (partly from remorse) and they were disavowed and ordered destroyed by USIF regulars. They've come back for revenge.
The eponymous Alpha Protocol doesn't exist for the purpose of providing deniable assets to the U.S. government. Also, Steven Heck claims to work for a branch of the CIA that doesn't officially exist, but he could just be crazy. (Steve is either the second best spy in the world, or crazy enough to be as effective as he is.)
Soldier of Fortune has The Shop, a covert government organization that conducts black operations around the globe.
In the Halo series, Section Zero is the completely-classified arm of the Office Of Naval Intelligence who handle its Internal Affairs, and have a functional license to kill anyone they have to in pursuit of their missions; they 'erased' hundreds of soldiers and test subjects and burned huge numbers of files when they buried the failed Spartan-I Program. Even within ONI, they're regarded as an urban legend at most.
More seriously, Area 51 was a real life subversion for most of its existence, as it was at least official enough that the President of the United States had to sign off on its budget every year. Though what they get up to is anyone's guess. The theories that the typical man on the street knows about all boil down to "Aliens!", but those more grounded in reality speculate that it's where the Air Force tests the cutting-edge technology of tomorrow, like stealth planes were in the Eighties. It's even possible that the alien conspiracy theories are actually encouraged because they obfuscate what's actually going on at the base: the aforementioned cutting-edge technology. On August 16, 2013 Area 51's existence was confirmed by the US government. It was, in fact, used to test the Lockheed U-2 stealth plane, and reportedly their programs resulted in an increase of UFO sightings in the area.
The British Secret Intelligence Service, more famously known as MI-6, wasn't officially acknowledged to exist until 1994 (though thanks to their long association with the James Bond franchise, pretty much everyone knew about them anyway). In his 1976 book The Governance of Britain, outgoing Prime Minister Harold Wilson had a chapter devoted to the SIS... which was one paragraph long and can be summed up as "An organisation exists, is funded by the taxpayer, and that's all I'm saying".