I'm with the guy who said he did 3-5 50-100m strides almost daily starting at only a moderately fast pace until it got easier. Hills are a good idea, too, though I think you also have to build into them very slowly. I am not over 40, but I suspect many of the people recommending something resembling the short, all out hill sprint are not 40+ either. It's a relatively recently wide-spread popular training element. Not to say there aren't examples of people doing this stuff a serious while back (Coe, for instance), but just that it's gotten popular recently. Jumping into all out hill sprints makes you sore when you are a college kid. It will probably be a bad idea for you. Building up very slowly--that sounds helpful. Really, there is more than one way to define the parameters of frequent, short duration, high intensity training.
Another thing to consider, with the debate going on between static/active stretching, etc, is that running faster requires a larger range of motion naturally. The closer you're getting to a sprint, the more your hips are going to extend and flex. That said, if you say you have a very high stride rate, your natural impulse might just be to run like a water lizard when you start to go faster. Still, your ROM will increase, but resist that urge. The best way to do this is not to reach with your lead leg trying to cover more ground, but just trying to put more force in the backward direction while your foot is on the ground. In this sense, I think a mixture between flat and hills (or even gradual downhills, as one poster suggested) will help your body stumble upon the slightly more efficient sprinting form it is capable of. (Aka learn a pattern of muscle recruitment). Think of it this way: when your glute fires really hard when your foot hits the ground, your hip is going to extend more (the femur of your contact leg will be at a great angle behind you). Your leg isn't going to extend backward without the other leg matching its movement (unless there is something seriously wrong with your stride). So, your knee will come up higher. It won't happen over night, but if you keep with it, it will improve.
That said, I know that plenty of studies say static stretching is worthless. But all the ballet dancers I've ever known have stretched extremely frequently and diligently to maintain their flexibility, and personally I've increased my range of motion by prolonged static stretching (20 minutes of sustained light stretching daily). Usually studies on stretching for runners don't actually focus on whether it has anything to do with range of motion. I remember at least one study that claimed to show that increases in range of motion led to decreased running performance. Most runners don't and probably shouldn't stretch for increased range of motion, but I think it is possible to do and that sometimes it needs to be done.
Good luck.