I don't use mercenaries unless it is absolutely necessary, with the exception that I'll sometimes hire my own factional troops so they can fight while I get the infrastructure up to train more. An example would be samnitici milites as the Romani. I prefer troops that I can produce in significant numbers and retrain to take advantage of experience gained. I try to strike a balance with my standard troop types between quality and the logistical challenges of getting them retrained and back to the front lines as quickly as possible - so no cohors evocata (trainable only in Italy) as the post-Marian Romani. There are times though when I'd love to have mercenary lugoae, or a similar poor but numerous unit, available for garrisoning new conquests. I have yet to be in a situation when an important arm has been completely unavailable and necessary to recruit mercenaries for, but (to use the Marian Romans as an example again - can you guess who I'm playing and how far I've got?) I could see that happening with cavalry in some theatres in my current game.

One answer to the problem of long supply lines and travel times for reinforcements is to not require them. Enter a theatre with sufficiently overwhelming force to completely overrun it. This done, head home, retrain and march to the next theatre. Not always possible, I'll grant, but when it is it works nicely.
I usually have no problem getting units recruited in Italy out to the far reaches of the expanding republic. Like, If Rome just recruited a unit of principes, then you can set it up so it will march to Arretium, freeing up a unit there to march to the next city, which frees up a unit there to march even further, etc. etc.
But this is expensive. You're using good troops to garrison cities, rather than larger, cheaper units when only the number of men present affects public order. You'd be better off force-marching the principes all the way and garrisoning your cities with leves.