Half of the characters in The Amazing Screw-On Head fit this formula, and the other half seems to: the titular Mr. Head, his former manservant Mr. Manifold turned archnemesis Emperor Mr. Zombie, and his new manservant Mr. Groin.
Mrs. Who, Mrs. What and Mrs. Which in A Wrinkle in Time. Justified in that they're not quite human.
The Undertaking in Kim Newman's Diogenes Club stories, an Edwardian version of the Men in Black, has agents with names like Mr. Hay and Mr. Bee, continuing down at least as far as Mr. Eggs.
The Witchfinder Army in Good Omens employs a long list of these. Justified in that none of them actually exist and are merely Line-of-Sight Names written on the payroll by Witchfinder General Shadwell, who is not known for his creativity, in order to get more pay then the Witchfinder Army's real 2-person roster warrants.
The Maunts (Nuns) in Literature/Wicked take names based on their proffesion in the Mauntery: Sister Doctor, Sister Apothecary, Sister Hammer, Sister Cupboard, Sister Cook, Sister Condiment(?), Sister Grave.
Used by a lot of musicians. Mister Joker, Mr. Mister, Mr. Kite, Mister Monster, Mr. Leen, Mr. Bones, Mr. Gang, Mr. E...
And speaking of Mr. Kite, The Beatles have a song titled "Being for the Benefit of Mr. Kite", which is based on a real life circus poster which included the titular line
In calypso, a common trend was for musicians to call themselves "Lord ____," starting with Lord Kitchener but moving into Strangenoun territory with Lord Beginner, Lord Invader and others. Many Carnival revelers took on high-faluting names, either to suggest nobility (as above), ferocity (Mighty Tiger), both (Black Stalin), and...well...whatever Red Plastic Bag was going for.
Some of the names in Rowan Atkinson's routine with the teacher taking attendance. The clean version has people named Undermanager and Haemoglobin; the dirty version has Clitoris ("Where are you, Clitoris?") and Herpes.