You don't need lot's of having power a new transaction with a higher transaction fee can get you there ~10-20% of the time. For small anonimus transactions like a vending machine that's not a problem. Add a slick UI and an suddenly lot's of people are going for random "Free" soda.
I think there are a mix of reasons why existing double spends are working, certainly things have gone wrong and there are various ways to do it - e.g. Eligius does not follow the same rules as everyone else and that's exploitable by double spenders. However that's not fee related.
