The odd couple: Mackenzie Crook and Mark Gatiss are back together again

British TV comedy seems like it must be a small pond, what with the same familiar performers frequently popping up in different programmes. As I recall, the BBC made an engaging documentary, Comedy Connections, on that very theme. So, as I stroll to a rehearsal room in London's Southwark to meet Mark Gatiss and Mackenzie Crook, I'm hoping that they do at least know each other already. Maybe they once sat on neighbouring tables at the Baftas. Maybe Gatiss, lately of The League of Gentlemen, will have been introduced to Crook by, say, Martin Freeman, the latter's co-star from The Office, who also features alongside Gatiss in Sherlock.

Maybe Catherine Tate – who performed with Gatiss in last year's National Theatre production of Alan Ayckbourn's Seasons Greetings, and with Crook in the long-defunct, late-night Channel 4 sketch show, Barking – once had them both round for dinner. (How's that for a comedy connection?) The pair are working together on a new production of The Recruiting Officer at the Donmar Warehouse but, given that it's only week two of rehearsals, and that Gatiss's character doesn't turn up until 45 minutes into the show, there's no guarantee they've played any getting-to-know-you games yet. Will I have to do the honours?

As it turns out, I can partially dispense with the small-talk: they've worked with each other before, on a project that even my extensive pre-interview research failed to throw up. "We made a film together called Sex Lives of the Potato Men," says Crook, a tad sheepishly. "It was very badly received at the time." If anything, that's an understatement: "Cringe-inducingly nasty," said Empire; "One of the two most nauseous films ever made," said The Times; "Would be unspeakably vile if it wasn't so embarrassingly puerile" – the BBC; "Mirthless, worthless, toothless, useless," said the Evening Standard. Crook recalls seeing his face on the news when the film flopped spectacularly, taking with it £1m of Lottery funding.

According to Gatiss, "It has the distinction of being only the second thing to appear in the Daily Mail under a headline including the words 'filth' and 'fury' – the first being the Sex Pistols". Since its disastrous release in 2004, however, the film has become "a cab drivers' favourite", Gatiss goes on. "I was walking my dog on the beach when I was at home in the north-east over Christmas, and this bloke stopped dead to stare at me. As soon as he opened his mouth and said, 'Ay, I was watching you in...', I knew he was going to say [Potato Men], because it happens so often."

Both men's fortunes have improved somewhat since then. This, their second joint venture, comes directly after some of the best work that either has done. Gatiss doesn't just act in Sherlock, as the titular detective's political-fixer brother, Mycroft; he also writes some of its episodes. Crook, meanwhile, has spent the past two-and-a-half years appearing onstage in London and New York, as Ginger in Jerusalem, the most rapturously-received play of the decade. How do you follow that?

Answer: with The Recruiting Officer, which has its own auspicious history. Its writer, George Farquhar, quit acting after he injured a fellow performer in a stage fight. (He'd forgotten to exchange his real sword for a dummy one during a scene change.) He had better luck as a playwright; his Restoration comedy blockbusters included The Constant Couple (1700); The Twin Rivals (1702) and The Beaux' Stratagem (1707). The Recruiting Officer, a romping satire of love and war, replete with bed-hopping, fiancée-swapping and cross-dressing, was originally performed in London in 1706.

More famously, in 1789, Farquhar's was the first play performed in New South Wales, Australia, by the convicts of the first colonial fleet – a production later immortalised by Timberlake Wertenbaker's 1988 play, Our Country's Good. The Recruiting Officer was also the first play to be performed professionally in America, at the New Theatre in New York in December 1732. The theatre belonged to the city's then acting governor, one Rip Van Dam, and the New England and Boston Gazette reported that "the part of Worthy [was] acted by the ingenious Mr Thomas Heady, barber and Peruque maker to his Honour".

Bertolt Brecht also adapted Farquhar's text as a play with music, Trumpets and Drums, the first premiere of his final season with his celebrated theatre company, the Berliner Ensemble. The Donmar production will be significant, too, as the first show to be staged by the theatre's new artistic director, Josie Rourke, who recently took the helm from Michael Grandage following his 10-year tenure. "It's a play that has been used to open a lot of theatres," she says. "And it's a really wonderful ensemble play; so it was an opportunity for me to go to a group of actors whom I knew to be fantastic." Also among the cast are Tobias Menzies, Rachel Stirling and, as Worthy, one of the romantic protagonists, Nicholas Burns – best known to connoisseurs of comedy connections as "self-facilitating media node" Nathan Barley.

"It's one of the most fun rehearsal rooms I've ever been in," says Rourke. "As a director you collect a sense of what actors can do through seeing their work elsewhere, and if you see someone deliver something brilliant, you keep it in your mind for years. I saw Mackenzie in a three-hander at the Bush Theatre called The Aliens, in which he gave a performance of total perfection and plausibility... Mark was fantastic in Season's Greetings, and he's a Renaissance man with a huge relish for and understanding of language and text."

Gatiss confirms as much: "I always wanted to do Restoration comedy," he says. "It seems like so much fun. I get to say 'Split me!'. I've always wanted to work at the Donmar, and nearly have a couple of times previously. I had to text Michael Grandage to say, 'I hope you won't read anything into the fact that I'm doing the very first show since you left!'."

The Recruiting Officer will also be a departure for Crook, whose previous stage work includes Jerusalem, The Seagull, and One Flew Over the Cuckoo's Nest – all of which, he explains, "demanded a degree of realism. I like to think of myself as a method actor, but it's hard to apply the method to something that was written 200 years before Stanislavski even came up with the idea. This is more like cabaret, big and broad, so it's more helpful to think back to my days as a stand-up."

It's hard to imagine that Crook spent 10 years on the stand-up circuit, albeit not as himself, but as characters such as "cheeky chappie from Chorley" Charlie Cheese, and tyrannical schoolteacher Mr Bagshaw. For an actor, let alone a comedian, he's remarkably shy and retiring. As a teenager, he had his heart set on being a graphic artist, and recently published his first illustrated children's book.

"I wasn't that into television and film," he says of his Kent childhood. Born in 1971, Crook recalls, "I grew up in a household that banned ITV, so I missed out on a bunch of stuff. I remember people talking in the playground about these amazing shows like Starsky and Hutch and The A-Team. Anything American was frowned upon in my house, I guess."

Not until he was 20 did a friend suggest he join a local theatre company. "It hadn't occurred to me to be an actor. I didn't know anybody who did it, and no one suggested it as a viable occupation. I've never regretted not going to drama school, but the one thing I feel I missed out on is a deep knowledge of plays and playwrights. I haven't seen or read the majority of Shakespeare's plays. I didn't know The Recruiting Officer until I was sent it for this production. It's a big gap in my knowledge that I've only just started to fill."

The more garrulous Gatiss, on the other hand, was unknowingly preparing himself for his career from a tender age. Born in Sedgefield some five years before Crook, he was an avid reader of Sherlock Holmes, and an avid watcher of Doctor Who, for which he now also writes. "I did go to drama school, at Bretton Hall in Yorkshire, but it was such a bad course that we had to fall back on our own devices," he recalls. He and three fellow students – Reece Shearsmith, Steve Pemberton and Jeremy Dyson – created a live sketch show, The League of Gentlemen, "which we took to Edinburgh, won the Perrier Award and got ourselves a radio series".

Like Crook, who finally found fame as Gareth in The Office, Gatiss made his name playing oddballs. "It's a cliché," he admits, "but it's true that all the fun lies in baddies, grotesques and comic roles. For me, the joy of The League was in the dressing up; the wigs and teeth. Now I get asked to play vicars all the time. I've only ever played one. I got offered three gay vicars in a day last year. I thought, 'Hang on, I'm not the new Nimmo!'. But as an actor, you know very early on if you're never going to play Romeo. And after that, it never enters your head."

It's no coincidence, of course, that his rise has been accompanied by a re-acceptance of the geek in popular culture, which can only be good for his and Crook's career prospects. Doctor Who, for which Gatiss is partly responsible, has undoubtedly driven this resurgence. "Sci-fi and fantasy used to be a TV staple throughout my childhood," he agrees. "Then it just stopped dead. It was seen as culty, a minority interest. The massive success of Doctor Who has opened all those doors again. It's no longer to be sneered at; in fact, people get worried if you don't have genre credentials. Geek preoccupations have become incredibly mainstream – even the geek look is cool. I do get that slight feeling of 'my favourite band's too popular' when I hear people talking about these things and don't quite believe that they're real fans!"

There is one geek ambition that he has yet to realise, however: his own action figure. "The toys I never had as a boy, because they didn't exist, are now taking over my life," he says. "There's an invasion of amazingly beautiful Doctor Who toys in my house. It's like crack. I've got about 30 daleks. When I was finally in Doctor Who as Professor Lazarus, they sent me a photo of a maquette they'd made for a figurine of the character. It was beautiful, but they make a series of maquettes before deciding which ones to manufacture and which to discard. And they never made mine!"

When pushed, Crook modestly admits that he has been immortalised in plastic; there's an action figure of Ragetti, his character from Pirates of the Caribbean. As a child, though, he was more interested in collecting live specimens than toys. His boyish love of nature remains, and a few years ago he bought himself five acres of Essex woodland as a conservation area.

"I manage it, and coppice it, and try to make it as attractive as I can to native wildlife," he explains. "When I bought it, it was very dense and nothing had been done to it in nearly a century. So I opened up some areas to let light down to the floor, which encourages different types of flora, which in turn encourages invertebrates and then birdlife. It's gradually becoming more diverse. Hopefully I'll be able to pass it on to my children. I read somewhere that Mick Hucknall has a forest called the Forest of Hucknall. Maybe I should call mine the Forest of Crook!"

Or "Crookswood", suggests Gatiss, nodding along in sympathy. "It's important to please your inner eight-year-old. The things that used to make you happy tend to be the things that still make you happy. I've got massively back into collecting fossils like I did when I was a child. And I just bought my brother-in-law a telescope for Christmas, of the size and strength that I always wanted and never had. We went out into the back garden and looked up at Jupiter; it was profoundly moving, because all I ever wanted as a boy was to see Jupiter and its four main Galilean moons. They're like little diamonds."

By this time, the two of them are getting on famously without me, so I begin to make my excuses. "I was just looking at Jupiter's moons the other day," Crook tells Gatiss, as I'm putting away my notebook. "I have a lovely telescope now, which I wanted when I was a kid. And I loved fossils as well. We'll have to have a fossil conversation..."

'The Recruiting Officer' is at the Donmar Warehouse, London WC2, from 9 February