The Leg of Mutton and Cauliflower's name certainly goes back to the 60s, thus predating the trend for silly contrived names. I don't know how much further back it goes though.

Didn't Mike Harding start this trend in his monologues in the early 70s, or was he just heading up something that was already happening? I remember the Pig and Ball Bearing in one of his pomes.