As a total amateur and probably the least-expert person in the discussion, FWIW, it seems to me that the number of patches necessary to get a 'good' ICC printing profile depends on three things:
(1) how linear / well-behaved the printer + ink + paper + driver settings the combination at issue is;
(2) how 'smart' the software is about the areas where errors are most visible and predicting the printer's least-linear areas, and concentrating patches in those areas; and
(3) your personal standards of good.
I tend to suspect that if you had a (presumably mythical) totally linear printer, then theoretically you could get a good profile with 27 patches: every permutation of each of red, green, and blue at minimum value, midpoint, and maximum value.
I've been pleasantly surprised at how well the X-Rite software for my lowly ColorMunki Photo works by printing and measuring a standard set of 50 patches, analyzing the areas most in need of refinement, and then custom-building a second set of another 50 (for color profiles) or 100 (for B&W-oriented profiles) patches and printing and measuring those. But this is an iterative process (print-measure-calculate-second print-second measure-build profile), and the typical process (print-measure-build profile) is not. My sense, quite possibly wrong (and please correct me if so), is that more than a few profiles have been built with 'dumb' patch sets. E.g., a 1728-patch set can be built as a 12x12x12 matrix of the permutations of reg, green, and blue from minimum to maximum; and a 729-patch set as a 9x9x9 matrix.
I'm definitely not a master printer--far from it! I do have good physical color acuity, and a propensity to notice color issues that even others who can (if shown) see them tend not to notice. You experts' experiences and opinions on this would be much appreciated.