I just took Cyrenacia from the Almos. You cannot build Saharans without a fort even though you have a horse breeder. Same applies for everything else - though you might have the buildings, without a basic fort there's no recruitment (unless there's an inn). So, the point is to get the AI to build the fort in the first place, but it doesn't since it already has the building that it wants to have - a HB. So, we're back at the start - get them to upgrade castles. I think it's best to add forts (or villages for VI) to all provinces, and will definitively do that next time around.