They probably weren't on commercial radio in the 80s, but they were on a major label (Verlaine and Lloyd solo as well) and geared toward the college market. I first heard Marquee Moon in college in the 90s, but didn't get hugely into it until later. And yes, Verlaine was punk. Punk means a lot of things (as does jazz) and if you stay away from the corny-ass versions of either you'll be fine.