The four seasons that followed found Muldoon's native province marooned a long way from where they wanted to be. Their tendency to lose three matches out of every four ensured they finished three of those seasons bottom of the pile and, on the one exception, second from bottom.
Muldoon was there throughout those seasons when even he began to wonder whether the gloom would ever lift and how much he could endure, when Bruce Springsteen's plaintive words would be ringing in his ears: ''Hard times come around no more.''
None can have been harder than on a Friday night at Cardiff Arms Park in September 2008. Connacht disappeared without trace, beaten as they had never been beaten before or since, 58-0.
Adversity on that scale makes their rise from the depths to the pinnacle as Guinness PRO12 champions all the more inspiring. They have made the competition the most democratic of all as the fifth different winner in six years after Ospreys, Leinster, Munster and Glasgow Warriors.
They have made discipline such a virtue that nobody ought to have been surprised that, despite a testing opening onslaught from Leinster, Connacht conceded their first penalty five minutes before the end of the first half and only three more in the second.
In his moment of triumph, Muldoon would probably have recalled a flashback or two from the Cardiff Blues match as he delved through the mists of his memory. ''There have been times when I'd come off the pitch and thought: 'That's me done.'
''You think about moving on and then you think of where you're from and you start believing again. We understand who we are playing for and what we are playing for and that's a big thing.''
In May 2009, Leinster ended their season as champions of Europe, the first of three such titles in four years. Connacht ended theirs that same season in their natural habitat, a home defeat by Ulster in front of 1,425 spectators keeping them pinned to the bottom.
Muldoon, a Galwegian, naturally, from the market town of Portumna, was there but then he's always been there. Having defied the odds all season long, their captain saw to it that Connacht rose to the occasion, ensuring their coronation as champions of Ireland, Scotland, Wales and Italy in the grand manner.
Leinster were back on the stage where they won their first final and this was their tenth in seven seasons - four in Europe, six in the PRO12. Connacht hadn't won anything since the last of their three inter-provincial titles in 1965. More to the point, they'd never been in a final of any description.
They proceeded to score three times as many tries as their most fashionable opponents, each finished off in real style by their uncapped back three - Tiernan O'Halloran, Niyi Adeolokun and Matt Healy.
Had Connacht won by a wider margin, Leinster could not have complained. So much for the theory that Leinster's big-game savvy would be the decisive factor.
Typically, Muldoon played down the inevitable comparison of one implausible champion with another, Leicester City Football Club. "I don't think I'd put us in the same category," he said. '
"Maybe some will and I wouldn't be objecting but I'd say we had a better chance of winning the Guinness PRO12 than Leicester had of winning the Premier League.
"I'd be lying if I said I'd ever see a day like this, a day when we got the chance to be champions. To be greeted by a sea of green when we drove into BT Murrayfield and to have so many Glasgow fans waving their flags in support of us sent shivers down our spines. Phenomenal."
That was nothing compared to the excitement back home. It had gone midnight when they brought the trophy to its new home and yet an estimated 2,000 people had waited at Knock airport until the small hours of Sunday morning to greet the champions.
Untold thousands more turned out on that afternoon to witness the victory parade from the Town Hall to The Sportsground. Pat Lam had done some famous things as a player on behalf of Newcastle Falcons and Northampton Saints but never anything to compare with this.
The Connacht phenomenon began with his arrival from New Zealand as head coach along with Dave Ellis and Andre Bell. Jimmy Duffy, a former Connacht player, joined them as forwards coach in the collective pursuit of a new style and a whole new ball game.
Connacht would learn to love the rugby ball like they had never loved it before so that keeping it in hand became second nature. "It took us a while to buy into the game-plan," Muldoon said. "But we did so wholeheartedly and that required a lot of courage.
"We'd be in The Sportsground and from time to time we'd hear people say: 'Kick it. Kick it.' But we stuck to the plan and we've won the championship. Pat kept hammering home the point all week that there was to be no falling back on old habits."
Lam's sole concern came during a brief period when his team kicked away a bit too much possession for his comfort. "People would say: 'Why don't you be pragmatic and kick it?' We did that at times in the Final and because of that we were in danger of losing control for the only time."
Despite recurring disruption caused by injuries and the consequent late rearrangement of their backs, Connacht had the belief and all-round ability to take it in their stride.
They used 46 players throughout the campaign, including a whole host from the Academy. The 23 on duty for the Final included 14 from Ireland. Of those, eight are Connacht born and bred - Robbie Henshaw, Ronan Loughney, Eoin McKeon, Andrew Browne, Sean O'Brien, Dave Heffernan, O'Halloran and Muldoon.
Connacht Guinness PRO12 champions - the bare facts:
Most starts (maximum 24):
23 - Bundee Aki.
22 - Matt Healy, Tiernan O'Halloran
21 - John Muldoon
19 - Tom McCartney.
Most appearances (including as a substitute):
24 - Finlay Bealham (10 starts)
23 - Aki, Muldoon.
22 - Healy, O'Halloran, Aly Muldowney (17 starts)
21 - Kieran Marmion (16 starts)
20 - McCartney
19 - Rodney Ah You (10 starts)
Tries:
10 - Healy.
6 - Adeolokun, O'Halloran, Aki
4 - Marmion.
Points:
89 - Craig Ronaldson
71 - Jack Carty
50 - Matt Healy
47 - AJ MacGinty
Follow the Guinness PRO12 on Facebook, join the conversation on Twitter, sign up to our YouTube channel for extensive match highlights and sign up for our newsletter for regular updates on the Guinness PRO12.
63x46.png){kind=logo}