I agree that regressive taxes (actual govt. issued taxes or implied taxes like smoking in your argument) are a tough case - especially when the people they most affect are sometimes strong supporters of the tax not being stopped.

Lottery games are an example of this - the people who play are overwhelmingly poor. This article argues that lottery spending may even be the single largest tax poor families pay [1].

With regard to what you say about there being no replacement income for governments if people stopped smoking cigarettes - I'd say this is only the case if consumption was banned. If it was slowly phased out the pain wouldn't be noticeable. It's like autonomous vehicles - what really matters is the speed of creative destruction.

[1] http://metrocosm.com/could-the-lottery-be-the-largest-tax/