There is actually a difference in meaning between the similar-looking phrases:
Im Gürtel hatte er ein Messer und zwei Pistolen stecken.
In den Gürtel hatte er ein Messer und zwei Pistolen gesteckt.
Im Gürtel hat er ein Messer und zwei Pistolen stecken.
In den Gürtel hat er ein Messer und zwei Pistolen gesteckt.
The different cases of Gürtel give a first clue: One expression signifies presence, the other one movement.
The verb stecken is a verb that explains a kind of movement — at least as long as the physical objects are also grammatical objects (it changes if the knife and the two pistols become a subject). The meaning is to stick something into something. This perfectly explains the second and fourth sentences: They are perfect and pluperfect forms of ‘He stuck a knife and two pistols into his belt.’ The movement requires accusative.
However, the original sentence is not trying to convey that meaning; instead, it wants to say that the weapons are there right now, without going into detail who put them there when and how. For that, technically, the verb haben would be enough, although it has a broader meaning (just being there; I’ll come back to that in a second).
Im Gürtel hatte er ein Messer und zwei Pistolen.{acc}
This way of expressing it loses the distinction between the knife and the two pistols sticking in his belt in plain view or being hidden in some clandestine pouch of his belt. That is where the two-part verb stecken haben comes in. I briefly mentioned above that we can make the weapons subjects which would mean ‘they are sticking in the belt’:
Im Gürtel sind ein Messer und zwei Pistolen{nom} gesteckt.
The verb stecken haben now allows us to include a reference to him (who may have been the subject of previous sentences or will be the subject of following ones) in subject case. Basically, you can understand it as being a crossover of the verbs stecken (in the weapons-nominative example) and haben: ‘he had a knife and two pistols sticking in his belt.’ This also explains the use of dative for the belt.