They had been the clown princes of Irish rock; three cheery Cork lads who had married indie sounds with irreverent attitude and garish attire. By 2003, though, the Frank and Walters had precious little to smile about.

Three unproductive years had passed since the band’s last studio album, a greatest hits compilation had scarcely caused a blip and they had been let go by Setanta Records, the London Irish label that had been their home for more than a decade. Little wonder, perhaps, that the trio — the bassist and singer-songwriter, Paul Linehan, his guitarist brother, Niall, and the drummer, Ashley Keating — were unsure about their future.

So when Niall Linehan announced he was leaving the band, it should have been the final nail in the coffin, particularly given the group’s uncertain mood. But far from finishing the Frank and Walters off, it allowed them to start afresh. Beneath the happy-go-lucky image, it seems, relationships had never been as chirpy as they appeared.

“To be honest, myself and my brother hadn’t got on in music since the start,” says Paul. “We were as bad as the brothers in Oasis or the Kinks; it goes back to sibling rivalry. But I think that maybe with Niall it was his time to go out. Maybe he wanted to go out before that, but it wasn’t pleasant when we worked together. I just think we have a chemistry that we don’t get on. Since he’s left we’ve made up a bit and it’s a bit better.

“And I had lost heart and that’s probably another reason he might have left. I’ve a feeling that Niall was thinking, well, the band is over, because for a while I wasn’t writing any new songs. But I just dusted myself down and got up again.”

“It was weird,” adds Keating, “because the Keith Cullen thing with Setanta happened (Cullen was the record label’s boss) — it was like, ‘Okay lads, we’ve come to the end of the line’ — and then the Niall thing happened.

“It was almost like a marriage breaking up, because we’d been with Niall and Keith for years and suddenly it was taken away. Though I always expected it to go this way, when it did happen it was very strange. So this is in a sense drawing a line under that. Now it’s phase two.”

Although the band have been through a traumatic period, as new beginnings go, the return of the Frank and Walters is a low-key affair, with a jarring sense of déjà vu. For their forthcoming tour, Linehan and Keating, both 38, will perform new material, with the guitarist Kevin Pedreschi replacing Niall, but the band’s latest album, Souvenirs, is a muted fanfare.

Far from marking any new direction, it is a retrospective, scattershot double CD of unreleased tracks, alternate mixes and rare B-sides. The album, released on the Irish independent label Fifa, unearths some previously lost indie pop nuggets and typically zany cover versions, such as a take on rapper Tone Loc’s Funky Cold Medina, but it is hardly ground-breaking stuff. While Linehan may pitch the album as a “bridge forward”, a way to reintroduce the band into the public eye before they return to the studio to record new material, Keating admits that, as a calling card, Souvenirs is “a bit of an oddity”.

Then again, the Frank and Walters have always been a bit of an oddity themselves. The surprising thing is not so much that they are still on the go a dozen years after their commercial peak, but that they enjoyed any success at all: the wide-eyed charm of early hits such as After All and Fashion Crisis Hits New York was accompanied by a jocular innocence that bordered on the gormless.

The band formed in Cork in the late 1980s, and Linehan recalls that on their first trip to London, in 1990, they visited every record company headquarters they could find to ask for a deal, all the while dressed in their trademark orange and purple outfits. Perhaps unsurprisingly, they failed in their quest: “We targeted a lot of the majors, but we got nothing out of it,” says Linehan. “That was our mistake. I don’t think we knew we were an indie band, but we figured it out after a while.”

But after signing to Setanta (and briefly to Go! Discs), the group’s chirpy singles and quirky image became unlikely chart material, yielding UK Top 20 hits. They were soon being chased by the labels who had earlier rejected them. They became regulars on Top of the Pops and played to packed houses, a development that took the band by surprise as much as anyone else.

“We never thought it would go that far and it was hard to fathom that so many people were taking you seriously,” says Linehan. But if the band seemed poised for wider success after the initial impact of Trains, Boats and Planes, their 1992 debut album, their career stalled.