Batting wise, people bring up a number of county legends - Stuart Law, Di Venuto, Matthew Elliot, Michael Love, etc. as players who could have played for any team, but couldnt get into the Aussie side in that period.
So lets take it as a given that they were pretty well stocked there. But bowling wise...
There was a growing dependence on McGrath and Warne.
Look at the series they played against India in 2004 - without the two of them, India managed to draw the series. They got 350 plus scores in every 1st innings. The only time they scored less than 400 in the 1st innings - they lost.
With McGrath and Warne there, I doubt they would have been able to consistently rack up such scores.
The bowlers they had as replacements were not up to the mark. MacGill is rated by the English - but lets face it, they are crap players of spin. In the aforementioned India series, he failed - took 14 wickets across 4 matches at 50. Kumble, on the other hand took 24 wickets over 3 games at 29.
The other bowlers used in that series...Bracken, Brad Williams and Brett Lee were not great test bowlers.
In the 2005 Ashes series, when McGrath went and Gillespie proved ineffective, it was left to Warne alone to try and push Australia through. Again, ultimately, it wasn't enough.