The question of how many color patches are necessary for a good printer profile depends on the color mode, printer's characteristics, the profiling software, and how intelligently the patches were chosen. For the sake of argument, let's define the minimum target patch count as the number of patches where adding an additional 200 (or 10%, whichever is larger) makes no visible difference in profile accuracy or, more often, output smoothness and resistance to visual artifacts. Relative, eyeball-gauged profile accuracy can most easily be assessed by neutrality of grayscales. Visual artifacts include abrupt transitions or banding in shadows and smoothness in the transitions to maximally saturated colors. If a profile shows hue shifts - blues turning purple or reds going orange - this indicates far too few patches or, more likely, poor profiling software.
The single largest factor in determining how many color patches are necessary is the output color mode. RGB has three degrees of freedom, CMYK four, and n-color more still. A basic color sampling strategy is to pick color points spaced evenly from the lowest to highest possible values. Building a sampling space containing 9 points on each axis requires 729 points for RGB (3 axes, so 9^3 = 729). The same grid interval for CMYK requires 6561 color patches (9^4 = 6561). Yes, ink limiting may reduce the total number of CMYK points, but the fact stands that you need significantly more color samples to describe a CMYK printer than for one that uses RGB input. Intelligent patch distribution is a must for CMYK or n-channel printers. I'll only talk about RGB-mode profiling from now on, primarily because that is what I am well-versed on.
A well-behaved printer, one that does not show abrupt transitions in color, density, or tone, can be profiled using a smaller array of patches than a less predictable device. Non-linear output can be modeled accurately only by having a sufficiently fine mesh of evaluation points. A predictable printer can be adequately profiled (using our above definition of no visual improvement after adding more patches) with as few as 729 patches with Monaco Profiler or PMP. Prime examples of such a printer were the Fuji Pictrography series. Looking through our measurement DB, the fewest patches see us using for a Pictro profile using Argyll was 1500. This work dates back a few years, but not that much has changed in terms of Argyll's fundamental behavior.
Typical inkjets benefit from at the Profiler maximum target of 1728 patches or as much as 4096 for PMP. This assumes a regular RGB grid spacing of 12 points for the 1728 patch count target or 16 for the 4096. Using the default RGB target that Argyll spits out, I agree with VitOne: 2000 patches is the minimum you need to use.
Building a target that concentrates on problem areas can reduce the necessary patch count. Profiler uses fixed layouts, but PMP (and i1Profiler) allow customized targets. A good starting point is the neutral axis. All our targets include many neutral patches and near-neutrals - e.g. R=0. G= 0, B=15, (7, 7, 15), ... , (239, 239, 255). Repeat for red, green, C, M, and Y. Additional points can be added in areas where the printer behavior gets non-linear. Argyll benefits from this technique.
A slightly different approach is to first characterize a small target to determine the printer's basic behavior then use that information to optimize the color patch distribution for the main target. ProfileCity originated this method; it has since been used by DataColor, ColorMunki, and Argyll. At the cost of making multiple measurements and generating unique targets for each printer, you can create a superior accuracy profile from fewer overall patches. This is what Iliah describes above as the first step in his profiling flow.
Argyll is the only package I am aware of that splits the correction curves calculated from the initial lin target apart from the profile. They need to be manually inserted into the profile later. This makes the math somewhat easier but seems like an unnecessary step to me. Since we build profiles on a remote basis, the attractions of an iterative approach are outweighed by the practicalities of only requiring customers to print a single target. This means we either needed to print a huge target, compromise on accuracy with a smaller patch set, or get clever with how we weight and process the data. We went the latter route, the details of which would only interest serious geeks.