my wife has the same issue. when we got her new car 6 months ago. I bought 4 of the regular boxes, opened the tops and put it in each of the footwells. Took care of the problem. I got the idea from a long time ago when someone bought a used car that smelled like cigarettes. The reply was the baking soda trick. So i tried it with my wife 6 months ago and it worked just a great.
good luck.