"by identifying abnormally heavy users and removing them" - That costs money, ergo, theft. It's like if someone had to hire a security guard for a vending machine.
DNS tunnelling is not fast or convenient. Places deploying captive portals have probably looked at the risk to their business from it and have decided not to worry about it.
I can't believe that using a slow DNS connection, intentionally made public, to tunnel traffic would be considered theft or criminal.
How many free samples do I have to eat before I'm a theif? I don't believe I'm a thief until the offer for free samples is rescinded.