During the mid-23rd century, the Bureau of Planetary Treaties attempted for many years to coerce the Gideon Council to allow them to send diplomats to their planet in effort to persuade the Gideons to join the Federation. Their council, however, consistently refused the presence of a delegation from the Federation on its soil, and or any surveillance by the ship's sensors.
Following the disappearance of James T. Kirk during beam-down, the Gideons refused to allow any further attempts at transport or searching for Captain Kirk. Spock consulted Starfleet Command for instruction, who in turn, consulted the Bureau of Planetary Treaties. Annoyed with the bureaucratic and diplomatic run-around he was getting from both Starfleet and the Gideon Council, Spock attempted to contact the Bureau directly, but was insistently told that he must go through Starfleet channels. (TOS: "The Mark of Gideon")