It’s 18 years since Stewart Lee and Richard Herring first played the Edinburgh festival, though you wouldn’t guess it to look at them. They’re no spring chickens – Lee is 37, Herring 38 – but they haven’t got the glazed nervousness of many festival veterans, or so many booze-broken veins. With just hours to go until their solo shows, Lee looks alert but relaxed, if perhaps a tad constipated; the only word to describe Herring is sleek. With their sunglasses and their black zip-up tops, you might take them for the kind of modern rock stars who prefer herbal tea to cocaine.

That might be appropriate, given that when Lee and Herring were on their way up, comedy was being described as the new rock’n’roll. But if ever they shared that view, they were disabused of it at the end of the 1990s. After two successful TV series, Fist of Fun and This Morning With Richard Not Judy, they had the plug pulled on them by the BBC. “We got treated so badly,” says Herring. “It got cut off just as it was getting somewhere interesting.” As performers, they have never again been so famous, though Lee’s involvement with the “blasphemous” Jerry Springer – the Opera has earned him a certain notoriety.

The woman they blame for all this is Jane Root, then controller of BBC2. “It was really frustrating in as much as the shows got really good reviews,” says Lee. “It was just the person taking over who didn’t like them.” The corporation justified its decision on the basis of poor audience figures, leading the comedians to claim that the scheduling was so erratic even they didn’t always know when their programme was going out. Does it still rankle? You bet.

But in a funny way, they also have reason to be grateful to Root. If she had commissioned a third series, they might have ended up crushed under the kind of fame now visited upon Little Britain’s Matt Lucas and David Walliams. “I don’t think either of us would have enjoyed that level of notoriety,” says Herring, wincing at the thought of punters yelling out “Moon on a stick!” a la “Yeah but no but … ” “I think Stewart would probably have killed himself.”

“It was probably a narrow escape,” Lee agrees. “I really didn’t like it when we were D-list celebrities and people shouted things at us in the street.” Still, he wouldn’t mind a little more material success. He describes how his friend Walliams cruised past him in a sports car full of blonde models, all waving and laughing. “That really cheered me up,” he says gloomily.

But that’s not what it’s all about. As comedians who started out in the alternative 1980s (they met while studying at Oxford university), Lee and Herring retain that era’s contempt for the sell-out. “There’s nothing we’ve done that we’re embarrassed about,” says Lee. “I think if we’d started doing lots of adverts or presenting the National Lottery people would have been disappointed.”

Who did take the money and run? Ben Elton, Herring says without a second’s hesitation. Younger readers may know Elton as a novelist and the man behind the rock musicals We Will Rock You and Tonight’s the Night, but he was once seen as a radical comedian, a shiny-suited challenge to Thatcherite values. They’re keen to see how he handles his return to stand-up later this year.

“The most interesting thing about Elton in the last five years,” says Lee, “is the way that he’s become a despised figure. You know you have to give titles to your stand-up shows; if I was Ben Elton I’d call it Fascinating Betrayal and try and justify my position. Instead, I expect he’s going to dismiss that and then talk about fatherhood, or try and regain a bit of ground. It’ll be like the elephant in the living room: you can’t discuss Ben Elton’s massive boil of hypocrisy that needs to be lanced.”

It has been a bumpy ride since This Morning With Richard Not Judy. Herring made good money writing for Al Murray’s TV series Time Gentlemen Please, and produced a book, Talking Cock, inspired by his own live show about penises. Lee directed a pilot or two for TV, and Simon Munnery’s BBC2 series Attention Scum!, which was nominated for a Golden Rose of Montreux award. There was no shortage of work, though usually as individuals rather than as a double act. But things had a way of turning sour. Herring felt let down by the way Talking Cock was marketed. Lee had a flashback as Jane Root (her again) cancelled Attention Scum!

Herring kept faith with Edinburgh, but last year’s show, The Twelve Tasks of Hercules Terrace, “was all about getting depressed and wondering where your life’s going”. Lee, meanwhile, welcomed the new millennium by giving up stand-up entirely. The audiences for his live shows had begun shrinking almost as soon as he disappeared from TV. “I just started to feel I was drifting above the stand-up, not really involved, so I quit and just wrote for newspapers and lived off what I’d saved.”

Then he got diverted by Jerry Springer – the Opera, the show that he co-wrote with the comedian and musician Richard Thomas. A cult hit at London’s BAC, containing a reported 8,000 obscenities, it became a succès de scandale after being picked up by the National Theatre, transferring to the West End and finally being broadcast by BBC2. Only last year did Lee find both the time and the inclination to return to live comedy.

He wasn’t overawed by the thought of working with the National. As the director of Jerry Springer, he was asked how he would scale up a production that had been created for the far smaller BAC – and said that he would hire bigger actors. But as someone who has spent much of his life defending a “low” artform from “highbrow” critics, Lee felt vindicated by his opera’s success. One critic, he recalls, talked of a fringe sensibility jumping into the mainstream. “Now, whenever that happens, these things tend to work. When the BBC finally had the confidence to put Harry Enfield on BBC1, it got 8m viewers. Likewise Absolutely Fabulous.”

Even comedians underestimate their audiences, Herring points out. “I have two sets, and I’ll sometimes go into the easy cock-joke set if I think there’s no point in trying, but the majority of people really want something clever and interesting and different – on TV and elsewhere. Most people are really up for it.”

“Most”, of course, is not “all”. The BBC’s decision to broadcast Jerry Springer – the Opera provoked a protest campaign spearheaded by the pressure group Christian Voice. More than 60,000 complaints were received, and death threats were made to BBC executives.

Given Lee’s disdain for established religion, you might have expected him to relish the controversy. Not a bit of it. “We never tried to cause offence,” he maintains. “He was very upset by it,” agrees Herring, himself a confirmed Christian-baiter. “But I’m amazed he wasn’t delighted. Just think – to have the most complained-about TV show ever!” He savours the irony of the BBC, which had spurned the duo six years before, getting payback in this roundabout way. “I think that’s just a fantastic turnout.”

After radio shows, TV, books, and highly structured live shows, this year they’re both back to comedy at its simplest – two entertainers trying to make people laugh. If they ever did want to be superstars, that’s no longer the case. “My ultimate ambition is to carry on working until I die,” says Herring, “and being massively successful can actually stop you doing good stuff.”

“I remember being here in 1987,” Lee says, “and seeing Arthur Smith, Jerry Sadowitz and Malcolm Hardee, and thinking, ‘That looks like a really good life – to be able to keep coming back to Edinburgh, doing increasingly strange but sustainable things.’ You start off thinking you’d like to be Ben Elton, then you look at what happened to him and you think, ‘That’d be awful.’ Being Arthur Smith – that’d be fantastic.” Looking back at it, he says, “The 1990s were kind of a write-off. First comedy was the new rock’n’roll. Then there was lad thing. Then you had the increasing dominance of commercial chains like Jongleurs. If you look at the circuit now, there’s a lot of little weirdos scrabbling around, setting up their own little places. It’s a lot more like the circuit that we caught the tail-end of in the 1980s.”

There are lots of exciting young people, too. They “sort of like” Lee and Herring. Not that they’re ready to relax yet. “Nearly always in Edinburgh there’s at least a day or two when you feel like throwing yourself off a bridge,” Herring says. “And there are lots of bridges here,” Lee points out.

· Stewart Lee is at the Smirnoff Underbelly, Edinburgh (0870 745 3083) until August 28. How To Write an Opera about Jerry Springer, featuring Stewart Lee and Richard Thomas, is at the Assembly Rooms (0131-226 2428) on August 16 and 17. Richard Herring is at the Pleasance Courtyard (0131-556 6550) until August 29.