I think you've all hit on some good explanations for cutting speed, but the one issue that isn't resolved regards metals that are purposely made "free machining" such as 303, or 416 stainless steel, leadloy, B16 (sometimes called CDA360) brass, etc...
These metals are much easier to machine, generally because of alloying elements such as sulfer. I've heard that sulfer for example, reduces the shear strength between crystals, but that still doesn't strike me as a complete answer because one might also expect that those materials would be much lower in shear and even in tension than the same materials without sulfer added, and that simply isn't true.
So why does the addition of sulfer or other alloying elements help increase machining speeds but have little or no affect on strength? For example, with the addition of sulfer to 304, we essentially get 303 with the same mechanical properties except for machinability which is increased by a factor of 2 or 3 (going from memory).