Clean the headliner, I bet that hasn't been done and that traps alot of the stink!Maybe the previous owner kept his stinky smoked fill jackets in the boot?
Many dealers use what's called a 'smoke bomb' to remove the smell. There like a fogger in a can, its a total release aerosol that is put in the car released and left to do its work, however they normally only mask the smell for a short while.
But this is supposed to be really good:
http://www.motorgeek.co.uk/dakota-odor-bomb-odour-eliminator-p-381.html
Another area to clean out is the steering column plastic shrouding, ash can falls behind it leaving a cigarette smell, also pull the drivers door card off as well, and if possible the area behind the ashtray.
Also definately change the pollen filter and spray in the recirculation bit whilst the heaters are on and then turn it off and onto recirc and spray into pollen filter too.