what type of interior does your clients vehicle have?
i have leather interior and i also smoke. however i too can not stand the smell of stale smoke. what i usually do is turn on the fresh air to get rid of the smell from all of my vents. air out the car and wipe down the whole interior top to bottom. usually gets ride of most of the smell, if not all.
iv heard of people trying fabreeze, smoke buster, or some type of air fresheners specifically for smoke and apparently they work ok.
later
-jeremy