Complex sentence: They soon encountered Bulk and Skull and agreed to become their butlers in exchange for shelter, but they were eventually located by Zedd and Rita, who restored their memories (and Goldar's wings).
Split into simpler sentences: They soon encountered Bulk and Skull and agreed to become their butlers in exchange for shelter. However, they were eventually located by Zedd and Rita, who restored their memories (and Goldar's wings).