I happened to be parked directly in front of a smoke shop that been there a year or so and I just today noticed a sign in the window that said "Gifts of all kinds."
I went in to talk to the owner, and sure enough, they have a great selection of laserable items, anodized lighters, wood cigar boxes, knives, glass items and more. He had never heard of a laser before, and after our chat he's anxious for me to go back with samples. I told him I could even engrave on a cigar (anyone tried that, did I lie?)