Muslims, in particular, have a history of using slave soldiers to good effect.

I seem to recall, and a glance over the Wikipedia articles suggests, that the Mamluk and Janissary systems involved raising (enslaved) boys into a military environment from a fairly young age. These boys might come from subjugated territories, but they'd in effect have been part of the dominant culture for much of their lives: it's not a system that could be used to quickly convert conquered territories into additional manpower.

That said, it hasn't been unusual for empires, modern and otherwise, to make substantial use of auxiliary forces drawn from client states. The Roman military probably relied on them as much as they did on the legions, or more in the late empire.