Defeat in the second round last season to Histon (who are they again?) only served to compound that total feeling of rejection.
That is until Sunday January 3, 2010 and a cold winter's day at Old Trafford. Leeds turned up in hope more than expectation - and why would they think any differently when their opponents were, in my opinion, the second best club side in the world, behind Barcelona.
True, Fergie didn't pick his strongest XI, but even a line-up consisting of Wayne Rooney and Dimitar Berbatov should really have had enough about them to see off their League One opponents.
OK, so the neutrals will say that Leeds put on a performance that belied their League One status, but anyone who witnessed their Carling Cup display against Liverpool earlier in the season knew a performance like that was comfortably in reach for Simon Grayson's side.
I don't want to get into all the old cliches about Leeds having '11 warriors on the park' but the tigerish displays throughout - and particularly those of Jonny Howson, Neil Kilkenny and Patrick Kisnorbo - deserve all the plaudits coming their way today.
Yes Leeds rode their luck, and I'm sure if the same game was played 10 times over, the Red Devils would win the next nine meetings. Rooney was clearly the hosts' best player by a country mile - and seeing him on a week-by-week basis makes me ever-more optimistic about England's chances this summer.
But Wazza aside, there was only really Anderson - and Ferguson made a huge tactical mistake removing him instead of the overrun Darron Gibson - who can leave that game with their head held high.
I doubt Wes Brown will face many harder games this season, with Jermaine Beckford's pace exploited perfectly by the Whites.
But all these factors, enhanced by a decent dose of good luck, helped contribute to one of the finest days in the modern history of Leeds. Well, when you have waited approaching 30 years for a win at Old Trafford, you have to allow the Whites their time in the sun - especially when the storm clouds have long since lingered over our once-proud club.
As for our old rivals over the Pennines, well, I can well believe reports that Ferguson delivered his famous hairdryer treatment following Sunday's defeat. But that's, partly, what makes him the successful manager that he has been and will continue to be. He doesn't take performances like that lightly. And, like it or loathe it, the success he has enjoyed during his 23-year stay makes him the best club manager the British game has ever seen. One defeat to Leeds does not change that.
Another reason behind his huge success is his ruthlessness in bombing out players who just don't cut the mustard. So if you are Gary Neville or perhaps even Dimitar Berbatov, Danny Welbeck or Gabriel Obertan you have a right to be feeling twitchy right now.
Either way, United will probably go on to win at least one trophy this term and give Ferguson another notch on his (still sturdy) bed post.
OK, so back to reality and we all know that Leeds are not going to win the FA Cup this season. Nor are we likely to celebrate another triumph at Tottenham in the next round. (If our former favourite Aaron Lennon is fit, I can tell you now that it's 'game over' because our full-backs just don't have 50% of his pace at jogging speed.)
But hopefully what we can take from this season, is promotion back into the second tier - with the win at Old Trafford serving as a huge confidence booster if nothing else.
And on a weekend when all cup upsets went out of the window, well done to Grayson and co for at least giving the neutrals something to smile about and prove the magic of the cup does still exist.