Mercenaries folow two set of rules as I see it.
For the player, it seems that mercenaries favour undeveloped lands close to a place where they were disbanded in the first place. Yes, disbanded... Try disbanding some units in a province with an inn. They'll be availible for hire. The pool of mercs from each inn gets its share, is filled with disbanded units (yours and AIs) and with a few random units. At the beginning of the game, since there are no disbanded units, computer adds some randomly in the choosing pool.
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... Talking about irony, eh...

However, try to get more advice from more experienced players, since I seldom use mercs myself. I rarely build inns in the first place, and I build them only for the happinnes bonus, not the merc option. I use mercs at the very beginning of the game, when there are still some very good units availible in the pool. I use them to expand myself rapidly and terror any neighbours in obedience. Later, I use them when I find myself desperatly defending against three or four strong factions and every bit of help is needed. Also I use them to help me when I need that extra bit of punch to kill a big faction. The turn I feel I don't need them, I disband them or send them on a suicide mission without looking back. Let the AI hire them again and pay the double support cost!