Well, you have to establish such protection agency first. You start your business, run advertising, etc. People come to you and pay for your services. Most people don't want to rob and kill other people, they want peace and protection, and they pay you for such things.

Now, what incentive do you have to blindly protect every robber who payed you? If you try to prevent punishment of a robber, your current(as well as potential) customers won't view your services as desirable, and simply won't pay you. Then you go out of business.

I think Murray Rothbard makes a better argument(while dissecting many common objections similar to yours). I recommend the chapter "Police, Law, and the Courts" from his book "For a new liberty: the libertarian manifesto" : http://mises.org/document/1010/For-a-New-Liberty-The-Liberta...