For the AI, there's a whole new song... It seems that AI gets to choose from the same units you choose and thus, if you aren't quick enough, the AI can buy them right under your nose. That would explain why you can't get them when you really need them. The AI probably filled it's ranks with mercs to attack you...
I've never seen the comp buy mercs, and I doubt the do considering that the merc symbol is seen even on "converted" (by a crusade) mercs.