From the Super Mario Wiki
They appeared in The Adventures of Super Mario Bros. 3 once, in the episode "Kootie Pie Rocks". In the episode, Cheatsy overhears the Mario Brothers talking about going to a rock concert with Princess Toadstool, for Milli Vanilli. Cheatsy made his way back to Castle Koopa and explained to Kootie Pie Koopa what the Mario Brothers intended to do. Kootie Pie was not pleased about the Princess getting something that she wasn't. In the middle of the band's concert, Cheatsy and King Koopa appeared in their Doomship and kidnapped the two singers, then made their way back to Castle Koopa. Kootie Pie wanted the two rock singers to sing for her but they refused. Kootie Pie was enraged, and she turned the two into accountants.
Milli Vanilli was the only guest appearance on The Adventures of Super Mario Bros. 3; whereas the preceding show, The Super Mario Bros. Super Show!, had several during the live-action segments.
Milli Vanilli were actually lip-syncers, and glitches in their equipment revealed this only two weeks after the initial airing of "Kootie Pie Rocks". Subsequent airings of the cartoon cut their songs and replaced them with different instrumental music. (Curiously, the pair still moved their lips while performing these wordless songs in the re-releases.) One of the episode's references to a Milli Vanilli song was also removed, and Milli Vanilli's song dedicated to Toadstool at the episode's end was completely cut, without even an instrumental replacement.
Though DVD releases of "Kootie Pie Rocks" generally censor the aforementioned Milli Vanilli references, the PAL "Do the Koopa" DVD retains Milli Vanilli's original songs if the language is switched to Dutch.