I think most strong dark beers would go well with smoke. (Although I'm more of a cigar guy myself - pipe tobacco makes my tongue feel like it's on fire!)
I think even a smoked malt-based beer might go well with tobacco smoke. (Although if I were to get a hold of another Alaskan Porter I would make sure my pallet was in peak form.) <!-- s;-) --><img src="{SMILIES_PATH}/icon_wink.gif" alt="

" title="Wink" /><!-- s;-) -->
I'm also going to vote for a coffee or espresso stout with tobacco.
And maybe a medium-dark highly phenolic belgian beer might work with smoke, too.
If you're looking for a home brew that would go with smoke I'd look for halfway in between a stout and a porter recipe (you want some residual sweetness ala crystal malt) and replace 20% of your base malt with Weyermann Rauchmalt (it's a very light smoke so if you go much lighter you won't even notice it in a dark beer) a bit of oats to give it that thick milkshake texture and some oiliness and it sounds like the perfect oily cigar pairing to me!
Adam