The opening episode of the 10th series, screened in the US on Wednesday, appeared to be a satire on Scientology.
Hayes, a Scientologist, quit the animated comedy after a different episode ridiculed the religion.
In the new show, Chef is brainwashed by the "Super Adventure Club" - thought to be a veiled reference to Scientology.
The other characters are angry at "that fruity little club for scrambling his brains".
Hayes did not participate in the episode but his lines were apparently patched together from previous recordings.
Chef arrives after travelling the world with the Super Adventure Club and repeatedly tells the children he wants to "make sweet love" to them.
The children take him to a psychiatrist and then a strip club, where he remembers his love for women and is cured.
But he is brainwashed by the Super Adventure Club again - before falling off a bridge and being burned, stabbed and mauled by a lion and a grizzly bear.
At his funeral, one of the children says: "A lot of us don't agree with the choices the Chef has made in the last few days.
"Some of us feel hurt and confused that he seemed to turn his back on us.
"But we can't let the events of the past few weeks take away the memories of how Chef made us smile."
Soul singer Hayes recently announced he had left the show because of its "intolerance and bigotry toward religious beliefs".
But co-creator Matt Stone said: "In 10 years and over 150 episodes of South Park, Isaac never had a problem with the show making fun of Christians, Muslim, Mormons or Jews.
"He got a sudden case of religious sensitivity when it was his religion featured on the show."
US TV network Comedy Central then pulled a different episode, which mocked Tom Cruise and more explicitly lampooned Scientology.
That prompted rumours that Cruise had demanded that the episode be dropped, which were denied by his representatives.
Hayes, 63, was admitted to hospital with exhaustion in January.