Police does not provide the service after the fact: you forgot about patrolling and deterrence it provides, for instance. What you describe is a particular case where service is bad. Well, there are bad waiters, too.
Your intuition is correct in at least one respect, however. Whereas private services are provided best by the markets, those same markets cannot provide public goods/services. A rational person would not want to pay anything for street lighting, for instance: once someone else pays for it, you'll be able to walk the same lighted street. (This is referred to as the "free-rider problem"). For that reason, government is needed to ensure provision of public goods: defense, public safety, sanitation, public schools, etc. You are correct, therefore, when you say that we don't pay for those voluntarily.
But the initial post was whether you get something or not. As I mentioned earlier, you do: police protection, lighted streets, sanitation, etc.
If patrolling were a deterrence then there would be a great reduction of crime. Facts are that crime is thriving quite nicely.
As I said previously, police don't prevent crime. Why? Because the criminals don't commit crimes when the police are around.
Therefore, the police arrive after the crime has been committed, i.e. 'after-the-fact'.