definitly leave some some headspace if you are force carbonating. the more headspace the faster it will carb.
I don't think it would matter with a regulator set as long as the surface area is the same.
Tell you what, try it for yourself. Set aside one keg with 1 in of head space and one with 4 inches and see which one carbonates faster. The more headspace for Co2 to fill the faster it will absorb if you are going with top pressure. This goes for the shake method too, the more headspace the less amount of time you have to shake. If you leave NO headspace the beer won't carbonate.
My guess is that what you're seeing is the effect of a smaller volume of beer carbonating faster. In other words, the volume of liquid rather than the volume of the headspace is the critical factor.
The appropriate test would be two different size kegs (a 5 gallon and a 3 gallon or whatever) with the same amount of beer in them. Identical volumes of beer should carbonate at the same rate. At least that's what makes intuitive sense to me.
As for no headspace, while I've not tried it, I have to think it would carbonate eventually if left hooked up to CO2 at constant pressure. However, if it's completely full the surface area that the gas would be in contact with might be as small as the dip tube.
As to the shake method, no disagreement. There's more surface area while you are shaking.