Up to 1/40 you don’t really need IS with a 35mm lens on full frame for stills.
The rest of what you have said is perfectly reasonable, but the above statement is at best outdated and at worst inaccurate. You might be able to hand hold some shots at 1/40 with a 35mm focal length, but generally you won't make full use of your 20mp or whatever.
Shake is quite random, but with the resolution of modern digital FF you really need to be in the region of 2x focal length. Even then you can get random shake. For really critical use nothing beats a genuinely stable mounting platform, but IS is a competent substitute up to a point. Personally I find IS very useful for stills when travelling without a tripod. It allows lower ISOs, greater dof, lower shutter speeds etc when hand held.
At pixel level with smaller pixels you might see a small difference.
The pixel pitch of my 5D mark III (22mp) is 36mm / 5760 pixels = 0.000625mm
The original 5D (12mp) has a pixel pitch of 36mm / 4368 = 0.000824mm
So the pixel pitch of a 22mp FF camera is just 132% of that of a 12mp FF camera.
If we apply the “old” rule of thumb 1/focal length we get 1/35 second for handheld shots. Multiply that by 1.32 and you get 1/46 of a second which is pretty close to the 1/40 I assumed in my previous post.
It’s just a rule of thumb and it depends on the photographers skill and the situation they are in how well this rule applies, but I see no technical reason to multiply it by 2 when using a 20mp camera.
The 2 times focal length rule might apply if you use the Sony/Nikon 36mp FF sensor or a future 40mp+ megapixel camera.
By the way, if we compare it to the analogue days: 36 mm x 24 mm film is estimated between 4 and 16 million pixels depending on the type of film used. Source: http://en.wikipedia.org/wiki/Digital_versus_film_photography
At the top end of the estimate, the difference is even smaller.