Considering that the cat does indeed "die" I guess it would go back to your hand... or maybe you just get a copy. That would actually be kinda cool.
Considering the cost involved in repeating that combo, I don't think it would be game breaking or anything. Just amusing.
(The cost of each kitty would be
plus this card's cost)
I would guess that otyugh would still grow as well... Its still eating something, the Djinn just returns its dead remains back to life with a wish.
...
Since I already have the lamp made anyway, what do you think about having the Djinn come from a permanent:
Magic Lamp 3
"Houses one Djinn. Djinn dies if lamp breaks.
: Call the Djinn to target slot or recall it to the lamp."
Then the Djinn can be:
Djinn 3
"Guards nearby allies. If one of them dies, return it to hand and Djinn to lamp (or owner's hand if no lamp was used)."
I.e. the Djinn card itself would not be available in the bazaar, only the lamp. Although you could still cast one as a normal creature if it gets returned to your hand.
... Or do you think that would be too complicated?