Why does allosteric binding produce a sigmoidal curve?
There is no tight link between allosteric binding and deviation from simple Michaelis-Menten kinetics.
Cooperative behavior of multi-domain proteins
What I do not understand is why does the velocity decrease so sharply at low concentrations of substrate?
The simplest model for the sigmoidal dependence of enzyme rates on substrate concentration (i.e. positive cooperativity) is a multi-subunit enzyme with multiple substrate binding sites. The enzyme has two states, both individually displaying Michaelis-Menten kinetics. However, the one with more efficient catalysis (larger $k_\mathrm{cat}$) is favored at higher substrate concentration. This is similar to hemoglobin switching to a higher affinity conformation as soon as some binding sites are occupied. This conformational change leads to a higher slope of rate vs. substrate concentration (or for hemoglobin, binding vs. ligand concentration) at the mid-point of the transition, allowing larger response of enzyme rates to substrate concentration (i.e. more sophisticated regulation). For an example, see ATCase. The enzyme has 6 active sites in different subunits, with conformational change explaining cooperativity. Complicating matters, it also has allosteric sites binding to other ligands, for additional regulation.
I get that allosteric binding should affect the shape - but this is not what I expected.
The image is misleading. For the cooperative effect in the model above, you expect binding of the substrate elsewhere (in another active site). Allosteric binding of a non-substrate ligand in an allosteric site generally does not switch the kinetics from Michaelis-Menten to non-Michaelis-Menten.
Cooperative behavior with a single active site
Glucokinase is an enzyme that shows cooperative kinetics (sigmoid rate vs substrate plot) without having multiple subunits or binding sites. This behavior is explained by slow conformational changes (in effect "memorizing" the there was a substrate recently). This means that when the number of reactions per time interval reaches a certain threshold, the enzyme will be faster because it is already in the "fast" conformational state. For a paper on possible mechanisms for this type of regulation, see doi:10.1016/j.bioorg.2011.11.001