Alright, you have a lot of good questions here. I won't be able to answer them all, since this would expand the discussion enormously, but I'll get through some of the points.
> I believe it's easier for the regulators in a free market system to get in bed with the regulated because those most motivated in regulating a specific industry are those within the industry itself.
You do know that ex-regulators and those closest to the political elite are usually hired by companies to serve as lobbyists (usually called something like "consultants" or "advisors")?
> You may believe it's obvious that consumers will switch to the better option in the market but the vast majority don't because the majority of people can't pay attention to everything they spend money on all the time.
Absence of a government doesn't mean people would need to waste more time tracking things. It means they would have a choice of who would track all these things for them. So, for instance, I subscribe to consumer protection agency A and it then simply drives my choices based on its research. People wouldn't need to choose everything by themselves.
Also, you can't excuse forcing people to do certain choices because they, allegedly, are not willing to make them on their own. It smells nanny state and unless you give people choice of experiencing why is it important to make choices and giving them time to make them, they will never learn. When slavery was abolished, many slave owners used to say that black people cannot survive on their own, they don't know how to work for money and how to spend it properly, so they would be much better off with their master. Indeed, in some cases that was true, because it's very difficult to learn to do things you never tried doing before. Eventually, they did learn.
> Instead consider what happens if for the sake of argument I forget my payment one month or I'm outside of my protection services city/village. Am I suddenly no longer protected and subject to others whims? Are there roaming fees for protection?
The way the market would work nobody can predict. What I can say is that it would find a way to provide you with what you need. One can imagine that when you go to a different territory you are protected by another company with which your company has a contract. If your company doesn't have a contract with another company or you are a poor person who can't afford protection, my guess is that you would still be able to count on some minimal level of protection: if people in my neighborhood are getting robbed, I as a paying customer of my protection agency would want them to prevent this happening regardless of whether the victim is their client or not, because next time it could be me.
Again, I think you have interesting questions, but I believe this discussion can go endlessly. At this point, I'd like to recommend you one book, it is called "The Machinery Of Freedom", written by David D. Friedman, who is an economist and a lawyer. In it, he thoroughly describes how a society without government would work. One of the most interesting chapters is about competing protection agencies and why they in fact wouldn't turn into de-facto government-like mafia. He also has some very interesting talks on YouTube which I recommend. I think this book would definitely be of interest to you. You may not be convinced by it, but it presents some great mental exercises and it would at least provoke you to look at the world from a different point of view. If it happens so that it does change your mind, please email me, I'd be very pleased to know that happened :)