The easy solution would be, rather than providing you with wealth, they actively drain wealth. You would still be "collecting taxes", but it would be offset by 1) the costs of garrisoning a very unruly populace and 2) the difficulty in actually taxing a populace that can disappear into the desert or etc. One of the things that the HIP mod for CK2 did that I really like is put a lot of negatives on a "recently conquered" province, which could be replicated.
Thus, for like the first 10 years the interior African province is a huge money pit, for another 10-20 it's still sucking a bit of money, then after that it has a low tax base. This can be changed by the populace converting culture and religion.
It's not a perfect solution, but there is a reason why it was difficult for the Iberian (and southern Italian) kingdoms to project force into North Africa over a sustained period. I would be concerned with it being an unfair malus on non-feudal realms in culturally diverse areas (Central Asia, Russia, etc.) so maybe have the system be much less severe for chiefdoms/khanates to represent their less direct control.
EDIT: The other major concern would be the AI, of course, as I would not expect it to understand that non-stop conquering is bad.