I though it possible that the Utility knife was once a cost-cutting alternative to buying both a Chef's knife and a Paring knife. So a "legitimate use", to answer my own question, would be, when you can only afford one knife. I looked into the history of this knife to see what truth there might be in this.
Amateur History of the Utility Knife
According to Merriam-Webster, the first known use of the term "utility knife" was in 1946. My own amateur efforts uncovered culinary uses of the term going back as far as 1921. It is only in 1940 that I find a reference to this knife where it is defined to any extent,
Utility knives. We believe every set should contain a knife suitable for general utility purposes-a blade somewhat longer than a paring knife's, so that it can slice tomato, cut grapefruit or melons and take care of dozens of cutting jobs. --Good housekeeping (1940)--Good housekeeping (1940): Volume 111, Number 3 p105 and p191
There was nothing in this article to suggest that a Utility knife should be considered as an alternative to owning more specialised knives. Quite the opposite, the reader is told thethat every kitchen should have a Paring knife, a Slicing knife, Carving knife, Bread knife, Butcher knife and a Utility knife.
The earlier references to Utility knives also follow this pattern,
The most important items of cutlery and small equipment for the kitchen include: One bread knife, One carving knife, One utility knife, Two small paring knives, One grapefruit knife [...] --The new book of etiquette (1924) Lillian Eichler Watson p179
The size of the blade varies between 4 and 8 inches depending on sources and at times itthis knife is confounded with both the Paring knife and the Chef's knife. The stated uses also vary, as would be expected from the name. To give just two examples,
Utiity 5" Slices, cuts and core fruits and vegetables; trims meats. --The Industry Leader Hardware Retailer (1968) p176
and somewhat more convincingly,
A six-to-eight-inch blade for cutting small vegetables, deboning chicken when a chefs knife is too clumsy and a paring knife to delicate --The home answer book (1995)
The rather curious conclusion (curious to me at least) is that the Utility knife appeared at a time when it was common to own a number of specialised knives. It seems that the Utility knife was as superfluous then as it is now. Nevertheless, Utility knives started to appear in product catalogues somewhere between 1924 and 1947 and increased in popularity from thereon.