(More a comment than an answer):
I've looked at the German Wikipedia entry wrt. the emergency numbers:
It's enlightening that 112 is both the European emergency number (since 1991) and in Germany it is also the emergency number for the fire brigade and the ambulance, historically (since 1973).
The police historically has used 110 (as explained in other answers).
I would assume therefore that, in Germany, 112 gets a lot more fire+medical traffic than the police one and is a possible explanation for the seeming incompetence of the operator - many locals would call 112 only for the fire and ambulance, and it's indistinguishable whether you intended the (historic) 112 or the international 112 :-)
Quite some other European countries have completely disjoint police/fire/medical emergency numbers vs. the international 112.