It's also part of the medley on the Paper Mario stage in Smash 3DS, if I'm not mistaken.
It's easy to say that now, but back when Kirby Super Deluxe was new, Marx was quite a surprising character. He fit in with all of the other random happy-go-lucky creatures and just appeared to be like any other character from the series. His betrayal of Kirby was something pretty unique in video games at the time, and it was genuinely surprising. This is why he's regarded as so memorable by so many, though I suppose you did have to be there at the time to get the full effect.
Don't feel frustrated about that, of all arguments!
I don't think anyone here can name any character who hasn't had that directed at them. It's very often code-speak for "I don't like that character, so I don't want to see them added.".
I support King K. Rool, Bandana Waddle Dee, Daisy, Mr. Stevenson, and Goku from Yuyuki, primarily. Ironically, it's only the first three (well-recognised characters who are popular) who get the "irrelevance" thing, whereas the latter two (who, to be fair, are all but forgotten) do not.