You have to find a weak point in Airbnb. Maybe focus on particular underserved cities. Maybe only allow amazing properties and aggressively poach them from Airbnb. Maybe try to enforce a common high-end experience by providing hosts with branded physical goods. Maybe piggyback on an existing hotel brand. Maybe market to the business market exclusively (worked for LinkedIn.) Just some quick ideas, and maybe not viable, but just cloning Airbnb isn't going to get you far.
Airbnb pushes out updates frequently, their site offers a great experience to the user, and they have a solid team of developers that stay ahead of the game. They're going to be here for a while.
As soon as they're big enough, they will start supporting these taxes and pushing for laws that require collection, as it makes it more difficult for others to enter the market the way they did.