You wouldn't need to do a *complete* overhaul of the system to make it work. It would just need to be changed so that it handles chocobos differently than it does players within a party. In programming each object, be it a player or NPC or box or whatever, is usually a part of one or more 'classes'. Right now it seems that chocobos do not have a unique class in terms of their treatment by the duty finder system. If you add a unique class for them to belong to that is ignored by the duty finder system in terms of matching that would fix one problem. Then just add a line or two of code that checks if any party members belong to the chocobo class and if so dismiss them from the parties of any participants before beginning the instance...

Of course in a game like this you get tons of interaction across processes and such there could be other intervening factors preventing a simple fix like this.