A good model for such a political structure would be the European Union. As an inter-national union rather than a national union of states (like the USA), it reflects your description pretty well: each member state remains sovereign, making its own laws and possessing its own government leadership, but they are bound together by certain shared judicial structures and military resources.
As the real world shows, such a union could be a source of conflict as well as cooperation. Social, political, or economic circumstances could cause tensions between stats, which must be resolved in order to preserve the union. And, as @ArtOfCode points out, each stats would operate as its own nation on the world stage, creating the possibility for political drama reaching beyond the bound of the union. Furthermore, there would undoubtedly be friction between the states and the apparatus of the union itself - individuals or groups at the state level might resent the union, which is nominally 'on top', while the union lacks the legal authority of a real supreme government. While the EU does have a common set of laws (most obviously the right of free movement of citizens within its member nations), it's easy to imagine a union which lacks the authority to establish a shared legal code (or perhaps to enforce it).
For a police/investigation bureau, a good model might be Interpol. Despite how it's portrayed in movies, it's not really a police force in the traditional sense - its main function it to facilitate cooperation between the police of its member states. Of course, you can play around with how much authority they have, and jurisdictional disputes among the states' forces and the union's force would doubtless arise on occasion.
In term of the military situation, there's a wide spread of possible setups. The European Union's military branch is pretty minimal, fitting its non-sovereign nature. If you wanted to beef it up, NATO would be a good model of a long-term international military operation, which troops drawn from various member nations. On the other hand, there's very little real armed conflict between EU states. You could go the other direction and ramp up military tensions, so that the union has to constantly work to keep its member states from falling into war. This might make sense especially if the union originated in response to some shared crisis which has since past, and its members are historically more enemies than allies.
The present-day EU has real problems, and sometimes seems to be teetering on the brink of collapse. Despite this, politicians from its member states have become experts at muddling through by way of compromise and appealing to their peoples' shared interests. Then again, these are democratic states; a union among less 'principled' nations could be significantly more volatile. In any case, I think the guiding principle is that such a union wouldn't be 'strong' per se, but flexible; it would be good at bending without breaking. If bent too far, however, most likely by internal war, it would be hard-pressed to put itself back together.